玩具取名「HAOI2008」

题意

给定一系列规则：某个长度为2的字符串可以化为某个长度为1的字符串。对于给出的字符串，求可以化为哪些长度为1的字符串。

题目所涉及字符串均由W,I,N,G组成。

---

思路

区间dp。

子状态(dp[l][r][i])表示区间[l,r]是否可以化为i。

枚举断点合并即可。

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

	template<typename T>inline void read (T &x) {
		x=0;T f=1;char c=getchar();
		for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
		for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
		x*=f;
	}

	template<typename T>inline void write (T x) {
		if (x<0) putchar('-'),x*=-1;
		if (x>=10) write(x/10);
		putchar(x%10+'0');
	}

}

using namespace StandardIO;

namespace Project {
	
	const int N=202;
	
	int n;
	int o,p,q,r;
	int trn[4][4][4],dp[N][N][4];
	char s[N];
	
	inline int trans (char x) {
		if (x=='W') return 0;
		if (x=='I') return 1;
		if (x=='N') return 2;
		if (x=='G') return 3;
	}

	inline void MAIN () {
		read(o),read(p),read(q),read(r);
		for (register int i=1; i<=o; ++i) {
			char a,b;scanf("%c%c",&a,&b);getchar();
			trn[trans(a)][trans(b)][0]=1;
		}
		for (register int i=1; i<=p; ++i) {
			char a,b;scanf("%c%c",&a,&b);getchar();
			trn[trans(a)][trans(b)][1]=1;
		}
		for (register int i=1; i<=q; ++i) {
			char a,b;scanf("%c%c",&a,&b);getchar();
			trn[trans(a)][trans(b)][2]=1;
		}
		for (register int i=1; i<=r; ++i) {
			char a,b;scanf("%c%c",&a,&b);getchar();
			trn[trans(a)][trans(b)][3]=1;
		}
		scanf("%s",s+1),n=strlen(s+1);
		for (register int i=1; i<=n; ++i) {
			dp[i][i][0]=(s[i]=='W');
			dp[i][i][1]=(s[i]=='I');
			dp[i][i][2]=(s[i]=='N');
			dp[i][i][3]=(s[i]=='G');
		}
		for (register int len=2; len<=n; ++len) {
			for (register int l=1,r=l+len-1; r<=n; ++l,++r) {
				for (register int k=l; k<r; ++k) {
					for (register int i=0; i<4; ++i) {
						for (register int x=0; x<4; ++x) {
							if (!dp[l][k][x]) continue;
							for (register int y=0; y<4; ++y) {
								if (!dp[k+1][r][y]) continue;
								if (!trn[x][y][i]) continue;
								dp[l][r][i]=1;
							}
						}
					}
				}
			}
		}
		int flag=0;
		if (dp[1][n][0]) flag=1,printf("W");
		if (dp[1][n][1]) flag=1,printf("I");
		if (dp[1][n][2]) flag=1,printf("N");
		if (dp[1][n][3]) flag=1,printf("G");
		if (!flag) printf("The name is wrong!");
	}
	
}

int main () {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	Project::MAIN();
}