1055: [HAOI2008]玩具取名
题目：传送门
简要题意：
就是固定四个字母，给出这四个字母分别可以由哪两个字母组成，然后在给你一个字符串，要求把这个字符串还原成原始的四个字母的其中一个。
题解：
一开始看题有点瞎...想了想是一道超级大难题...
其实就是一个很简单的DP...
定义发f[i][j][s]:表示在字符串中i~j这个区间是否可以组合成为字符s
转移很容易就可以想出来：因为如果f[i][k][s1]==f[k+1][j][s2]==1(i<=k<=j) && s1和s2可以组成s，那么f[i][j][s]=1;
O(n^4)...大水题
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
char s[];
struct node
{
char s1,s2,id;
}st[];
bool f[][][];
int main()
{
int W,I,N,G;bool bk=false;
scanf("%d%d%d%d",&W,&I,&N,&G);
int len=;
for(int i=;i<=W;i++)
scanf("%s",s+),st[++len].s1=s[],st[len].s2=s[],st[len].id='W';
for(int i=;i<=I;i++)
scanf("%s",s+),st[++len].s1=s[],st[len].s2=s[],st[len].id='I';
for(int i=;i<=N;i++)
scanf("%s",s+),st[++len].s1=s[],st[len].s2=s[],st[len].id='N';
for(int i=;i<=G;i++)
scanf("%s",s+),st[++len].s1=s[],st[len].s2=s[],st[len].id='G';
scanf("%s",s+);
int len1=strlen(s+);
memset(f,,sizeof(f));
for(int i=;i<=len1;i++)f[i][i][s[i]]=true;
for(int i=;i<=len1;i++)//长度
for(int l=;l<=len1-i+;l++)//左端点
{
int r=l+i-;
for(int j=l;j<=r;j++)//断点
for(int k=;k<=len;k++)//枚举所有种类的字符串
if(f[l][j][st[k].s1] && f[j+][r][st[k].s2])
f[l][r][st[k].id]=true;
}
W='W';I='I';N='N';G='G';
if(f[][len1][W])printf("W"),bk=true;
if(f[][len1][I])printf("I"),bk=true;
if(f[][len1][N])printf("N"),bk=true;
if(f[][len1][G])printf("G"),bk=true;
if(bk==false)printf("The name is wrong!\n");
return ;
}