水题大失败

原题：

某人有一套玩具，并想法给玩具命名。首先他选择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即可

注意无解

代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 int mf[210];  char _f[5]; 8 int b[5];  bool a[5][5][5]; 9 int t[210],lt=0;  char _t[210];10 bool f[5][210][210];11 int main(){
    //freopen("ddd.in","r",stdin);12     memset(f,0,sizeof(f));13     memset(a,0,sizeof(a));14     mf['W']=1,mf['I']=2,mf['N']=3,mf['G']=4;15     for(int i=1;i<=4;i++)  cin>>b[i];16     for(int k=1;k<=4;k++)17         for(int i=1;i<=b[k];i++){18             char _ch=getchar();  while(_ch!='W'&&_ch!='I'&&_ch!='N'&&_ch!='G')_ch=getchar();19             a[k][mf[_ch]][mf[getchar()]]=true;20         }21     scanf("%s",_t+1);  lt=strlen(_t+1);22     for(int i=1;i<=lt;i++){  t[i]=mf[_t[i]];  f[t[i]][i][i]=true;}23     /*for(int i=1;i