来自FallDream的博客，未经允许，请勿转载，谢谢。
某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。
100%数据满足Len<=200，W、I、N、G<=16
题解：很明显的区间dp,用f[i][j][k]表示区间[i,j]能否表示成第k个字母。
#include<iostream> #include<cstdio> #include<cstring> #define MN 200 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } bool f[MN][MN][4]; int s[MN+5];char st[MN+5]; int num[4],n; int c[4][17][2]; inline int getnum(char ch) { if(ch=='W')return 0; if(ch=='I')return 1; if(ch=='N')return 2; return 3; } inline int get() { char ch; do ch=getchar(); while(ch!='W'&&ch!='I'&&ch!='N'&&ch!='G'); return getnum(ch); } int main() { for(int i=0;i<4;i++)num[i]=read(); for(int j=0;j<4;j++) for(int i=1;i<=num[j];i++) c[j][i][0]=get(),c[j][i][1]=get(); scanf("%s",st+1);n=strlen(st+1); for(int i=1;i<=n;i++) f[i][i][s[i]=getnum(st[i])]=1; for(int len=2;len<=n;len++) for(int i=1;i+len-1<=n;i++) { int j=i+len-1; for(int k=0;k<4;k++) for(int l=1;l<=num[k];l++) { for(int q=i;q<j;q++) f[i][j][k]|=(f[i][q][c[k][l][0]]&f[q+1][j][c[k][l][1]]); } } bool flag=0; if(f[1][n][0]) printf("W"),flag=1; if(f[1][n][1]) printf("I"),flag=1; if(f[1][n][2]) printf("N"),flag=1; if(f[1][n][3]) printf("G"),flag=1; if(!flag)puts("The name is wrong!"); return 0; }