题目大意：给定一个由‘W','I','N','G'构成的字符串。给定一些规则。这些规则能够将两个字符合成为一个，比如"II"能够合成为'W'，"WW"能够合成为'I'或者'N'

求这个字符串能够终于合成为哪几种字符

看到这题我想到了广搜。

。。事实上不是必需，动归全然能够解决

令f[i][j][k]为从i開始的j个字符能否够合成为字符[k]

然后j从外层循环。剩下的所有预处理，怎么暴力怎么转移。我写了六层循环，有点吓人

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define M 210

using namespace std;

int n,W,I,N,G;

int trans[4][4][4];

bool f[M][M][4],flag;

char s[M],table[5]="WING";

inline int GetInt(char c)

{

	switch(c)

	{

		case 'W':return 0;

		case 'I':return 1;

		case 'N':return 2;

		case 'G':return 3;

	}

}

inline void Input(int p)

{

	int x,y;

	char c[2];

	scanf("%s",c);

	x=GetInt(c[0]);

	y=GetInt(c[1]);

	trans[x][y][p]=1;

}

int main()

{

	int i,j,k,c1,c2,c3;

	cin>>W>>I>>N>>G;

	for(i=1;i<=W;i++)

		Input(0);

	for(i=1;i<=I;i++)

		Input(1);

	for(i=1;i<=N;i++)

		Input(2);

	for(i=1;i<=G;i++)

		Input(3);

	scanf("%s",s+1);

	n=strlen(s+1);

	for(i=1;i<=n;i++)

		f[i][1][ GetInt(s[i]) ]=1;

	for(j=2;j<=n;j++)

		for(i=1;i+j-1<=n;i++)

			for(k=i;k<i+j-1;k++)

				for(c1=0;c1<4;c1++)

					if(f[i][k-i+1][c1])

						for(c2=0;c2<4;c2++)

							if(f[k+1][i+j-1-k][c2])

								for(c3=0;c3<4;c3++)

									if(trans[c1][c2][c3])

										f[i][j][c3]=1;

	for(i=0;i<4;i++)

		if(f[1][n][i])

			flag=1,putchar(table[i]);

	if(!flag)

		puts("The name is wrong!");

}