1055: [HAOI2008]玩具取名 区间DP

令 fi,j,k 表示 si..sj 是否能缩成字母 k ， k=0,1,2,3分别表示W,I,N,G 。
然后记忆搜一下。。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int len;
int f[205][205][4];
char s[205],a[4][17][2];
int q[255],t[4];
char p[4]={'W','I','N','G'};
inline int read()
{
    int a=0,f=1; char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}
    while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}
    return a*f;
}
bool dp(int l,int r,int k)
{
    if (l==r) return s[l]==p[k];
    if (f[l][r][k]!=-1) return f[l][r][k];
    for (int i=1;i<=t[k];i++)
        for (int j=l;j<r;j++)
            if (dp(l,j,q[a[k][i][0]])&&dp(j+1,r,q[a[k][i][1]]))
                return f[l][r][k]=1;
    return f[l][r][k]=0;
}
int main()
{
    memset(f,-1,sizeof(f));
    for (int i=0;i<4;i++) t[i]=read();
    q['W']=0; q['I']=1; q['N']=2; q['G']=3;
    for (int i=0;i<4;i++)
        for (int j=1;j<=t[i];j++)
            scanf("%s",a[i][j]);
    scanf("%s",s+1);
    len=strlen(s+1);
    bool flag=0;
    for (int i=0;i<4;i++)
        if (dp(1,len,i)) flag=1,putchar(p[i]);
    if (!flag) puts("The name is wrong!");
    return 0;
}