【HAOI2008】玩具命名

水题大失败

原题：

某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。
现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。

第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。
接下来W行，每行两个字母,表示W可以用这两个字母替代。
接下来I行，每行两个字母,表示I可以用这两个字母替代。
接下来N行，每行两个字母,表示N可以用这两个字母替代。
接下来G行，每行两个字母,表示G可以用这两个字母替代。
最后一行一个长度不超过Len的字符串。表示这个玩具的名字

如果给的名字不能由任何一个字母变形而得到则输出“The name is wrong!”

Len<=200，W、I、N、G<=16

因为之前水了几道HAOI的题，所以这次想了想直接开始码dfs，然后呵呵

然后上网搜题解了……

然后发现是区间DP，然后就又很水了……

用f[i][j][k]表示从i到j可以变成k

区间DP即可

注意无解

代码：

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 using namespace std;

 int mf[];  char _f[];

 int b[];  bool a[][][];

 int t[],lt=;  char _t[];

 bool f[][][];

 int main(){//freopen("ddd.in","r",stdin);

     memset(f,,sizeof(f));

     memset(a,,sizeof(a));

     mf['W']=,mf['I']=,mf['N']=,mf['G']=;

     for(int i=;i<=;i++)  cin>>b[i];

     for(int k=;k<=;k++)

         for(int i=;i<=b[k];i++){

             char _ch=getchar();  while(_ch!='W'&&_ch!='I'&&_ch!='N'&&_ch!='G')_ch=getchar();

             a[k][mf[_ch]][mf[getchar()]]=true;

         }

     scanf("%s",_t+);  lt=strlen(_t+);

     for(int i=;i<=lt;i++){  t[i]=mf[_t[i]];  f[t[i]][i][i]=true;}

     /*for(int i=1;i<lt;i++)

         for(int j=1;j<=4;j++)

             f[j][i][i+1]=a[j][t[i]][t[i+1]];*/

     for(int l=;l<=lt;l++)

         for(int i=;i<=lt-l+;i++){

             int j=i+l-;

             for(int h=i;h<=j-;h++)

                 for(int p=;p<=;p++)if(f[p][i][h])

                     for(int q=;q<=;q++)if(f[q][h+][j])

                         for(int k=;k<=;k++)if(a[k][p][q])

                             f[k][i][j]=true;

         }

     _f[]='W',_f[]='I',_f[]='N',_f[]='G';

     bool flag=false;

     for(int i=;i<=;i++)if(f[i][][lt])  cout<<_f[i],flag=true;

     if(!flag)  cout<<"The name is wrong!"<<endl;

     cout<<endl;

     return ;

 }