记录编号	288404	评测结果	AAAAAAAAAA
题目名称	[HAOI 2008]玩具取名	最终得分	100
用户昵称	Hzoi_chairman	是否通过	通过
代码语言	C++	运行时间	0.549 s
提交时间	2016-08-02 20:37:02	内存使用	2.89 MiB

#include<iostream>
#include<cstdio>
using namespace std;
int read()
{
	int x,f=1;
	char ch;
	while(ch=getchar(),!isdigit(ch))if(ch=='-')f=-1;
	x=ch-48;
	while(ch=getchar(),isdigit(ch))x=x*10+ch-48;
	return x*f;
}
char ch[]={' ','W','I','N','G'};
int a[10];
bool f[500][500][10];
bool c[100][100][20];
int main()
{
	freopen("name.in","r",stdin);
	freopen("name.out","w",stdout);
	a[1]=read(),a[2]=read(),a[3]=read(),a[4]=read();
	for(int i=1;i<=4;i++)
	{
		for(int j=1;j<=a[i];j++)
		{
			string s;
			cin>>s;
			int c1=s[0],cc=s[1];
			c[c1][cc][i]=1;
		}
	}
	string s;
	cin>>s;
	int n=s.length();
	for(int i=0;i<n;i++)
	{
		int c1=s[i],c2=s[i+1];
		for(int j=1;j<=4;j++)
		{
			if(s[i]==ch[j])f[i][i][j]=1;//注意不要用c1和j比较 
			if(c[c1][c2][j])
			{
				f[i][i+1][j]=1;
			}
		}
	}
	for(int d=3;d<=n;d++)
		for(int i=0;i<=n-d;i++)
		{
			int j=i+d-1;
			for(int k=i+1;k<=j;k++)
				for(int a=1;a<=4;a++)
					if(f[i][k-1][a])
						for(int g=1;g<=4;g++)
							if(f[k][j][g])
							{
								int c1=ch[a];
								int c2=ch[g];
								for(int e=1;e<=4;e++)
									if(c[c1][c2][e])
									{
										f[i][j][e]=1;
									}
							}
		}
	bool flag=0;
	for(int i=1;i<=4;i++)
		if(f[0][n-1][i])printf("%c",ch[i]),flag=1;
	if(flag==0)
	{
		printf("The name is wrong!");
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*
类似动规,枚举断点,左右两部分合成两个字符,再通过这两个字符合并
*/