核心思路

对于区间i~j，枚举中间点k。

枚举字母x,y,z，如果xy可以还原成z，那么如果i~k可以还原为x，k+1~j可以还原成y，那么i~j就可以还原成z。（不难理解）

i...k k+1...j
  |       |      i...k k+1...j
  x       y  =>    \_______/
   \_____/             |
      |                z
      z

WARN

码风奇特，如果思路懂了就别看我代码了。

Code

#include<iostream>
#include<map>
#define cntfor(n) for(int cntfori=1;cntfori<=n;cntfori++)
#define block(tips) 
using namespace std;
int main(){
	map<int,char>itc;//int to char
	itc[1]='W',itc[2]='I',itc[3]='N',itc[4]='G';
	map<char,int>cti;//char to int
	cti['W']=1,cti['I']=2,cti['N']=3,cti['G']=4;
	bool a[5][5][5]{};//i,j,k ij can return to k
	block("get a"){
		int n[5];
		cntfor(4){
			cin>>n[cntfori];
		}
		for(int i=1;i<=4;i++)
			cntfor(n[i]){
				char x,y;
				cin>>x>>y;
				a[cti[x]][cti[y]][i]=true;
			}
	}
	string name;
	cin>>name;
	int n=name.size();
	name='\0'+name;
	bool f[n+1][n+1][5]{};
	//l,r,k the interval from l to r can return to k
	for(int i=1;i<=n;i++)
		f[i][i][cti[name[i]]]=true;
	cntfor(n-1)
		for(int i=1,j=i+cntfori;j<=n;i++,j++)
			for(int k=i;k<j;k++)
				for(int x=1;x<=4;x++)
					for(int y=1;y<=4;y++)
						for(int z=1;z<=4;z++)
							if(a[x][y][z]&&f[i][k][x]&&f[k+1][j][y])
								f[i][j][z]=true;
	bool noans=true;//There is no answer
	for(int i=1;i<=4;i++)
		if(f[1][n][i])
			cout<<itc[i],noans=false;
	if(noans)
		cout<<"The name is wrong!";
	return 0;
}

记忆化搜索版

(递推版的看HYR的)

#include<bits/stdc++.h>
using namespace std;
int sw,si,sn,sg;
bool f[4][4][4];
int dp[205][205][4];
string s;
int tf(char x)
{
	if(x=='W')return 0;
	if(x=='I')return 1;
	if(x=='N')return 2;
	if(x=='G')return 3;
}
char ct(int x)
{
	if(x==0)return 'W';
	if(x==1)return 'I';
	if(x==2)return 'N';
	if(x==3)return 'G';
}
int dfs(int l,int r,int z)
{
	if(dp[l][r][z]!=-1)return dp[l][r][z];
	dp[l][r][z]=0;
	for(int k=l;k<r;k++)
		for(int x=0;x<4;x++)
			for(int y=0;y<4;y++)
				for(int z=0;z<4;z++)
					if(f[x][y][z] && dfs(l,k,x) && dfs(k+1,r,y))
						dp[l][r][z]=1;
	return dp[l][r][z];
}
int main()
{
	memset(dp,-1,sizeof dp);
	cin>>sw>>si>>sn>>sg;
	char a,b;
	while(sw--)(cin>>a>>b),f[tf(a)][tf(b)][0]=1;
	while(si--)(cin>>a>>b),f[tf(a)][tf(b)][1]=1;
	while(sn--)(cin>>a>>b),f[tf(a)][tf(b)][2]=1;
	while(sg--)(cin>>a>>b),f[tf(a)][tf(b)][3]=1;
	cin>>s;s=' '+s;int n=s.size()-1;
	for(int i=1;i<=n;i++)
		dp[i][i][tf(s[i])]=1;
	bool flag=0;
	for(int i=0;i<4;i++)
		if(dfs(1,n,i)==1)
			(cout<<ct(i)),flag=1;
	if(!flag)cout<<"The name is wrong!";
	return 0;
}

完整代码我就不发了，我在此贡献自己遇到的错误。

正确的核心代码如下：

// ok[x][y][z] 表示两个字母 xy 是否能被一个字母 z 代替
// f[L][R][z] 表示区间 [L,R] 能否由一个字母 z 经过若干次展开得到
for (int len = 2; len <= n; len++)
		for (int L = 1; L + len - 1 <= n; L++) {
			int R = L + len - 1;
			for (int k = L; k < R; k++)
				for (int x1 = 1; x1 <= 4; x1++)
					for (int x2 = 1; x2 <= 4; x2++)
						for (int x3 = 1; x3 <= 4; x3++)
							if (ok[x2][x3][x1] && f[L][k][x2] && f[k + 1][R][x3])
								f[L][R][x1] = 1;
		}

注意其中 if 那里，我原来WA的代码是：

if (ok[x2][x3][x1])
  f[L][R][x1] = f[L][k][x2] && f[k + 1][R][x3];

乍看两种写法没啥区别，但WA的代码只要 ok[x2][x3][x1]==true 就要执行一次合并计算，有可能在之前合并结果是 true，但在后面会有合并结果是 false 的情况（题目样例就能测出这个问题）。而正确代码是在保证 ok[x2][x3][x1]==true 并且左子区间和右子区间都能分别归并到字母 x2 和 x3 时才被赋值为 true，逻辑上还是不一样的。

仔细思考！！！警钟敲烂！！！