Description
某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后
他会根据自己的喜好，将名字中任意一个字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。
现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。
Input
第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。接下来W行，每行两个字母,表示W可
以用这两个字母替代。接下来I行，每行两个字母,表示I可以用这两个字母替代。接下来N行，每行两个字母,表示N
可以用这两个字母替代。接下来G行，每行两个字母,表示G可以用这两个字母替代。最后一行一个长度不超过Len的
字符串。表示这个玩具的名字。
Output
一行字符串，该名字可能由哪些字母变形而得到。（按照WING的顺序输出）如果给的名字不能由任何一个字母
变形而得到则输出“The name is wrong!”
Solution
用布尔数组f[i][j][k]来表示i到j的这段区间内能否用k表示。用w存储输入数据，读入的第i组信息是N可转换为IG，那么w[i][1]储存I，w[i][2]储存G，w[i][3]则储存N。还是看程序注释吧。
Code
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 bool f[222][222][5]; 9 int w[111][5],num;10 string s;11 int main()12 { 13 int a,b,c,d;14 cin>>a>>b>>c>>d;15 num=a+b+c+d;16 for (int i=1; i<=a; i++) w[i][3]=1;//用1 2 3 4分别代表W I N G17 for (int i=a+1; i<=a+b; i++) w[i][3]=2;18 for (int i=a+b+1; i<=num-d; i++) w[i][3]=3;19 for (int i=num-d+1; i<=num; i++) w[i][3]=4;20 for (int i=1; i<=num; i++)21 {22 cin>>s;23 switch (s[0])24 {25 case 'W':w[i][1]=1; break;26 case 'I':w[i][1]=2; break;27 case 'N':w[i][1]=3; break;28 case 'G':w[i][1]=4; break;29 }30 switch (s[1])31 {32 case 'W':w[i][2]=1; break;33 case 'I':w[i][2]=2; break;34 case 'N':w[i][2]=3; break;35 case 'G':w[i][2]=4; break;36 }37 } 38 cin>>s;39 int slen=s.size();40 memset(f,false,sizeof(f));41 for (int i=0; i<=slen-1; i++)42 switch (s[i])43 {44 case 'W':f[i+1][i+1][1]=true; break;45 case 'I':f[i+1][i+1][2]=true; break;46 case 'N':f[i+1][i+1][3]=true; break;47 case 'G':f[i+1][i+1][4]=true; break;48 }49 int r; 50 for (int len=2; len<=slen; len++)51 for (int l=1; l<=slen-len+1; l++)52 {53 r=l+len-1;54 for (int m=l; m<=r-1; m++)55 for (int k=1; k<=num; k++)56 f[l][r][w[k][3]]=(f[l][m][w[k][1]])&&(f[m+1][r][w[k][2]])||(f[l][r][w[k][3]]);57 } 58 int ans=0;59 bool fg=false;60 for (int i=1; i<=4; i++)61 if (f[1][slen][i])62 { 63 switch (i)64 {65 case 1: cout<<'W'; break;66 case 2: cout<<'I'; break;67 case 3: cout<<'N'; break;68 case 4: cout<<'G'; break;69 }70 fg=true;71 } 72 if (fg==false) cout<<"The name is wrong!"<