原题链接

题解

1.复杂问题简单化，把字符用数字代替
2.每次替换都会减少一个字符，到最后一定是由两个字符合成一个字符，并且这两个字符的来源区间不相交
3.相同区间不同的合并方式，最后生成的字符也不同，所以dp多加一个状态
4.题目只问能否合成对应字符

code

#include<bits/stdc++.h>
using namespace std;
int a[5]={0},can[5][5][5]={0},dp[205][205][5]={0};
int change(char c)
{
    if(c=='W') return 1;
    if(c=='I') return 2;
    if(c=='N') return 3;
    if(c=='G') return 4;
}
int main()
{
        for(int i=1;i<=4;i++)cin>>a[i];

        for(int i=1;i<=4;i++)
        {
            for(int j=1;j<=a[i];j++)
            {
                string s;
                cin>>s;
                can[i][change(s[0])][change(s[1])]=1;//i 是否能由【jk】得来
            }
        }

        string s;
        cin>>s;
        int len=s.size();

        s=" "+s;

        for(int i=1;i<=len;i++) dp[i][i][change(s[i])]=1;//[l,r] 能否变成i
        for(int k=2;k<=len;k++)
        {
            for(int l=1;l+k-1<=len;l++)
            {
                int r=l+k-1;
                for(int i=l;i<r;i++)
                {
                    for(int c1=1;c1<=4;c1++)//区间[l,r] 是否能够得到字符c1
                    {
                        for(int c2=1;c2<=4;c2++)//左半区间能否得到字符c2
                        {
                            for(int c3=1;c3<=4;c3++)//右半区间能否得到字符c3
                            {
                                if(can[c1][c2][c3]&&dp[l][i][c2]&&dp[i+1][r][c3])
                                {
                                    dp[l][r][c1]=1;
                                }
                            }
                        }
                    }
                }
            }
        }

        int flag=0;
        if(dp[1][len][1]) {flag=1;cout<<"W";}
        if(dp[1][len][2]) {flag=1;cout<<"I";}
        if(dp[1][len][3]) {flag=1;cout<<"N";}
        if(dp[1][len][4]) {flag=1;cout<<"G";}
        if(!flag) puts("The name is wrong!");
    return 0;
}