[文章目录]
Description
某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。len<=200
区间dp即可。dp[l][r][k]表示区间l,r是否可以从k变成。复杂度O(len^3)
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define pb push_back
int n,num[5];
bool dp[210][210][5];
char s[210];
struct node
{
int a,b;
};
vector<node>ve[5];
inline int id(char x)
{
if(x=='W') return 1;
if(x=='I') return 2;
if(x=='N') return 3;
if(x=='G') return 4;
return 0;
}
int main()
{
int i,j; char st[10];
for(i=1;i<=4;++i) scanf("%d",num+i);
for(i=1;i<=4;++i)
for(j=1;j<=num[i];++j)
{
scanf("%s",st);
ve[i].pb((node){id(st[0]),id(st[1])});
}
scanf("%s",s+1); n=strlen(s+1);
for(i=1;i<=n;++i) dp[i][i][id(s[i])]=1;
int r,k,c,v;
for(i=1;i<n;++i)
for(j=1,r=j+i;r<=n;++j,++r)
for(c=1;c<=4;++c)
for(k=j;k<r&&!dp[j][r][c];++k)
for(v=0;v<num[c]&&!dp[j][r][c];++v)
dp[j][r][c]|=(dp[j][k][ve[c][v].a]&dp[k+1][r][ve[c][v].b]);
if(dp[1][n][1]|dp[1][n][2]|dp[1][n][3]|dp[1][n][4])
{
if(dp[1][n][1]) putchar('W');
if(dp[1][n][2]) putchar('I');
if(dp[1][n][3]) putchar('N');
if(dp[1][n][4]) putchar('G');
}
else puts("The name is wrong!");
return 0;
}