bzoj1055: [HAOI2008]玩具起名儿

状态 F[i,j,k] 表示从第i位到第j位，是否可以变换成字符k

const int N = 210;
const char T[6] = {" WING"};
bool Dp[N][N][5];
char Dat[N];
vector<int> need[5][5];

inline int turn(char x) {
	if(x == 'W') return 1;
	else if(x == 'I') return 2;
	else if(x == 'N') return 3;
	else return 4;
}

int T_T[5];

inline void Input() {
	For(i, 1, 4) scanf("%d", &T_T[i]);
	For(i, 1, 4)
		For(j, 1, T_T[i]) {
			scanf("%s", Dat + 1);
			need[turn(Dat[1])][turn(Dat[2])].pub(i);
		}
	scanf("%s", Dat + 1);
}

inline void Solve() {
	int Len = strlen(Dat + 1);
	clr(Dp, 0);
	For(i, 1, Len) Dp[i][i][turn(Dat[i])] = 1;
	For(j, 2, Len)
		For(i, 1, Len - j + 1)
			For(k, i, i + j - 2)
				For(p, 1, 4)
					if(Dp[i][k][p])
						For(q, 1, 4)
							if(Dp[k + 1][i + j - 1][q])
								Rep(s, sz(need[p][q]))
									Dp[i][i + j - 1][need[p][q][s]] = 1;
	bool flag = 0;
	For(i, 1, 4)
		if(Dp[1][Len][i]) flag = 1, printf("%c", T[i]);
	if(!flag) puts("The name is wrong!");
}

int main() {
    #ifndef ONLINE_JUDGE
    SETIO("1055");
    #endif
    Input();
    Solve();
    return 0;
}