思路：

f[i][j][k]表示i到j匹配了字母k

if(m,n能匹配上k)

f[i][j][k]|=f[i][l][m]&f[l+1][j][n]

一个大枚举 就OK了~

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int W,I,N,G;

bool f[205][205][5],vis[5][5][5],flag;

char ch[3],goal[222];

int get(char x){

    if(x=='W')return 1;

    if(x=='I')return 2;

    if(x=='N')return 3;

    return 4;

}

int main(){

    scanf("%d%d%d%d",&W,&I,&N,&G);

    for(int i=1;i<=W;i++)

        scanf("%s",ch),vis[1][get(ch[0])][get(ch[1])]=1;

    for(int i=1;i<=I;i++)

        scanf("%s",ch),vis[2][get(ch[0])][get(ch[1])]=1;

    for(int i=1;i<=N;i++)

        scanf("%s",ch),vis[3][get(ch[0])][get(ch[1])]=1;

    for(int i=1;i<=G;i++)

        scanf("%s",ch),vis[4][get(ch[0])][get(ch[1])]=1;

    scanf("%s",goal+1);

    int len=strlen(goal+1);

    for(int i=1;i<=len;i++)f[i][i][get(goal[i])]=1;

    for(int le=1;le<=len;le++)

        for(int st=1;st<=len;st++){

            int ed=st+le;

            if(ed>len)break;

            for(int k=1;k<=4;k++)

                for(int l=st;l<ed;l++)

                    for(int m=1;m<=4;m++)

                        for(int n=1;n<=4;n++)

                            if(vis[k][m][n])

                                f[st][ed][k]|=f[st][l][m]&f[l+1][ed][n];

        }

    if(f[1][len][1])putchar('W'),flag=1;

    if(f[1][len][2])putchar('I'),flag=1;

    if(f[1][len][3])putchar('N'),flag=1;

    if(f[1][len][4])putchar('G'),flag=1;

    if(!flag)puts("The name is wrong!");

}