[HAOI2008]玩具取名
@[toc]

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。
现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。 输入描述:
第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。 接下来W行，每行两个字母,表示W可以用这两个字母替代。
接下来I行，每行两个字母,表示I可以用这两个字母替代。 接下来N行，每行两个字母,表示N可以用这两个字母替代。
接下来G行，每行两个字母,表示G可以用这两个字母替代。 最后一行一个长度不超过Len的字符串。表示这个玩具的名字。

输出描述:

一行字符串，该名字可能由哪些字母变形而得到。（按照WING的顺序输出） 如果给的名字不能由任何一个字母变形而得到则输出“The name
is wrong!”

示例1
输入

1 1 1 1
II
WW
WW
IG
IIII

输出

IN

题解

题目虽然输入的是字母，但是我们可以当做数字来处理
重要的两个数组，均为bool型
dp[i][j][k]表示区间[i,j]是否是由k转化而来的
can[i][j][k]表示i是否可以用 j k 两个字母代替
can是在读入时更新
我们想一想区间更新的条件：
区间[l,r],中间点为k
z，z1，z2为1~4，表示为WING
如果左区间[l,k+1]可以由z1转化（即代码dp[l][k][z1]），右区间[k+1,r]可以由z2转化(代码dp[k+1][r][z2]),
z可以用z1和z2来代替（代码dp[z][z1][z2]），那是不是就说明区间[l,r]是由z转化的
（相当于z1，z2是一个中转站，用来将区间[l,r]与z联系在一起）

套上区间dp的万能模板
就能得到

for(int i=1;i<=len;i++) dp[i][i][a[i]]=true;//从i到i可以由他自己转化

    for(int led=1;led<len;led++)//列举长度的可能性
        for(int l=1;l<=len-led;l++)//列举左界的可能性 
        {
            int r=l+led;//右界可以算出来
            for(int k=l;k<r;k++) //在左右之间列举可能的断点 
                for(int z=1;z<=4;z++)  //列举l到r（需要的区间）可能转化成的字母
                    for(int z1=1;z1<=4;z1++) // 列举l到k（借助的左区间）
                        for(int z2=1;z2<=4;z2++)  //列举k + 1到r（借助的右区间）
                            if(can[z][z1][z2] && dp[l][k][z1] && dp[k+1][r][z2]) 
//如果z1、z2可以转化成z 并且 l到k可以变成z1 并且k+1到r可以变成z2
                                dp[l][r][z]=true;
//那么l到r就可以转化成z
        }

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e2+7;
int dp[maxn][maxn][maxn];
bool can[maxn][maxn][maxn];
int p[maxn];
char s[maxn];
int a[300];
int change(char i){  
    if(i=='W') return 1; 
    if(i=='I') return 2;
    if(i=='N') return 3; 
    if(i=='G') return 4; 
} 
int main()
{
    a['W']=1;
    a['I']=2;
    a['N']=3;
    a['G']=4;
    for(int i=1;i<=4;i++)cin>>p[i];
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=p[i];j++)
        {
            char x,y;
            cin>>x>>y;
            can[i][a[x]][a[y]]=1;
        }
    }
    cin>>(s+1);
    int n=strlen(s+1);
//    cout<<n<<endl; 
    for(int i=1;i<=n;i++)dp[i][i][a[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 z=1;z<=4;z++)
                {
                    for(int z1=1;z1<=4;z1++)
                    {
                        for(int z2=1;z2<=4;z2++)
                        {
                            if(can[z][z1][z2]&&dp[i][k][z1]&&dp[k+1][j][z2])
                            dp[i][j][z]=1;
                        }
                    }
                }
            }

        }
    }
    bool flag=false;
    if(dp[1][n][1]) {flag=true;printf("W");}
    if(dp[1][n][2]) {flag=true;printf("I");}
    if(dp[1][n][3]) {flag=true;printf("N");}
    if(dp[1][n][4]) {flag=true;printf("G");}
    if(!flag) printf("The name is wrong!");
}