bzoj1055 [HAOI2008]玩具取名（dp）

f[i][j][t]表示si~sj能否变成字母t。区间dp即可。
复杂度 O(n3163) ，但是常数小可以过。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 210
int n,num[4],a[70][3],id['Z'],tot=0;
bool f[N][N][4];char s[N];
inline char print(int op){
    if(op==0) return 'W';
    if(op==1) return 'I';
    if(op==2) return 'N';
    if(op==3) return 'G';
}
int main(){
// freopen("a.in","r",stdin);
    for(int i=0;i<4;++i) scanf("%d",&num[i]);
    id['W']=0;id['I']=1;id['N']=2;id['G']=3;
    for(int i=0;i<4;++i){
        while(num[i]--){
            scanf("%s",s+1);a[++tot][0]=i;
            a[tot][1]=id[s[1]];a[tot][2]=id[s[2]];
        }
    }scanf("%s",s+1);n=strlen(s+1);
    for(int i=1;i<=n;++i) f[i][i][id[s[i]]]=1;
    for(int len=2;len<=n;++len)
        for(int i=1;i<=n;++i){
            int j=i+len-1;if(j>n) break;
            for(int k=i;k<j;++k)
                for(int t=1;t<=tot;++t)
                    if(f[i][k][a[t][1]]&&f[k+1][j][a[t][2]])
                        f[i][j][a[t][0]]=1;
        }bool flag=0;
    for(int i=0;i<4;++i) if(f[1][n][i]) flag=1,putchar(print(i));
    if(!flag) puts("The name is wrong!");
    return 0;
}