BZOJ-1055: [HAOI2008]玩具取名

Description

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

区间dp即可。dp[l][r][k]表示区间l,r是否可以从k变成。复杂度O(len^3)

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define pb push_back 
int n,num[5];
bool dp[210][210][5];
char s[210];
struct node
{
    int a,b;
};
vector<node>ve[5];
inline int id(char x)
{
    if(x=='W') return 1;
    if(x=='I') return 2;
    if(x=='N') return 3;
    if(x=='G') return 4;
    return 0;
}
int main()
{
    int i,j; char st[10];
    for(i=1;i<=4;++i) scanf("%d",num+i);
    for(i=1;i<=4;++i)
        for(j=1;j<=num[i];++j)
        {
            scanf("%s",st);
            ve[i].pb((node){id(st[0]),id(st[1])});
        }
    scanf("%s",s+1); n=strlen(s+1);
    for(i=1;i<=n;++i) dp[i][i][id(s[i])]=1;
    int r,k,c,v;
    for(i=1;i<n;++i)
        for(j=1,r=j+i;r<=n;++j,++r)
            for(c=1;c<=4;++c)
                for(k=j;k<r&&!dp[j][r][c];++k)
                    for(v=0;v<num[c]&&!dp[j][r][c];++v)
                        dp[j][r][c]|=(dp[j][k][ve[c][v].a]&dp[k+1][r][ve[c][v].b]);
    if(dp[1][n][1]|dp[1][n][2]|dp[1][n][3]|dp[1][n][4])
    {
        if(dp[1][n][1]) putchar('W');
        if(dp[1][n][2]) putchar('I');
        if(dp[1][n][3]) putchar('N');
        if(dp[1][n][4]) putchar('G');
    }
    else puts("The name is wrong!");
    return 0;
}