https://www.luogu.com.cn/record/111346171

#include<bits/stdc++.h>
using namespace std;

char s[205];
int w,i,n,g,len;
bool c[5],f[205][205][5];

vector<int> a[5][5],dp[205][205];

int cha(char x){  
    if(x=='W') return 1; 
    if(x=='I') return 2;
    if(x=='N') return 3; 
    if(x=='G') return 4; 
} 

int main(){
	//in
	scanf("%d%d%d%d",&w,&i,&n,&g);
	char ch1,ch2;
	for(int j(1);j<=w;j++){
		scanf(" %c %c",&ch1,&ch2);
		//cout<<ch1<<"*"<<ch2<<": "<<cha(ch1]<<"*"<<cha(ch2]<<endl;
		a[cha(ch1)][cha(ch2)].push_back(1);
		//for(int v:a[cha(ch1]][cha(ch2]])cout<<v<<endl;
	}
	for(int j(1);j<=i;j++){
		scanf(" %c %c",&ch1,&ch2);
		//cout<<ch1<<"*"<<ch2<<": "<<cha(ch1]<<"*"<<cha(ch2]<<endl;
		a[cha(ch1)][cha(ch2)].push_back(2);
		//for(int v:a[cha(ch1]][cha(ch2]])cout<<v<<endl;
	}
	for(int j(1);j<=n;j++){
		scanf(" %c %c",&ch1,&ch2);
		//cout<<ch1<<"*"<<ch2<<": "<<cha(ch1]<<"*"<<cha(ch2]<<endl;
		a[cha(ch1)][cha(ch2)].push_back(3);
		//for(int v:a[cha(ch1]][cha(ch2]])cout<<v<<endl;
	}
	for(int j(1);j<=g;j++){
		scanf(" %c %c",&ch1,&ch2);
		//cout<<ch1<<"*"<<ch2<<": "<<cha(ch1]<<"*"<<cha(ch2]<<endl;
		a[cha(ch1)][cha(ch2)].push_back(4);
		//for(int v:a[cha(ch1]][cha(ch2]])cout<<v<<endl;
	}
	/*
	for(int j=1;j<=4;j++){
		for(int k=1;k<=4;k++){
			if(a[j][k].empty())continue;
			cout<<j<<" "<<k<<" :"<<endl;
			for(int v:a[j][k])cout<<v<<endl;
		}
	}
	*/
	scanf(" %s",s+1);
	len=strlen(s+1);
	for(int j(1);j<=len;j++)
		dp[j][j].push_back(cha(s[j])),f[j][j][cha(s[j])]=1;
	//solve 
	for(int j(1);j<len;j++){
		for(int l(1);l+j<=len;l++){
			int r=l+j;
			for(int k(l);k<r;k++){
				//cout<<l<<" "<<k<<" "<<r<<endl;
				for(int d:dp[l][k])
					for(int p:dp[k+1][r]){
						//cout<<d<<" "<<p<<endl;
						for(int qwq:a[d][p])
							if(!f[l][r][qwq]){
								f[l][r][qwq]=1;
								dp[l][r].push_back(qwq);
								//cout<<qwq<<endl;
							}
					}
			}
		}
	}
	
	//out
	if(dp[1][len].empty())return puts("The name is wrong!"),0;
	if(f[1][len][1])printf("W");
	if(f[1][len][2])printf("I");
	if(f[1][len][3])printf("N");
	if(f[1][len][4])printf("G");
	return 0;
}

蟹蟹 qwq