$dp$
设 $f[i][j][k]$ 表示初始为 $k$ 时，能否得到 $[i,j]$ 这一段子串
设 $pd[i][j][k]$ 表示长度为二的字符串 $ij$ 能否由 $k$ 得到
然后枚举左右区间转移：有
$f[i][j][k]=[f[i][p][x]=1] and [f[p+1][j][y]=1] and [pd[x][y][k]=1]$
边界 $f[i][i][k]=[a[i]=k]$
然后直接记忆化搜索
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } int n[7],a[207],m; int pd[7][7][7]; char s[207]; bool f[207][207][7],vis[207][207][7]; inline int F(char s) { if(s=='W') return 1; if(s=='I') return 2; return s=='N' ? 3 : 4; } inline char DF(int x) { if(x==1) return 'W'; if(x==2) return 'I'; return x==3 ? 'N' : 'G'; } bool dfs(int l,int r,int x) { if(l==r&&a[l]==x) return 1; if(vis[l][r][x]) return f[l][r][x]; vis[l][r][x]=1; bool &T=f[l][r][x]; for(int i=l;i<r;i++) for(int j=1;j<=4;j++) for(int k=1;k<=4;k++) if(pd[j][k][x]&&dfs(l,i,j)&&dfs(i+1,r,k)) { T=1; break; } return T; } int main() { for(int i=1;i<=4;i++) n[i]=read(); for(int i=1;i<=4;i++) for(int j=1;j<=n[i];j++) { scanf("%s",s); pd[F(s[0])][F(s[1])][i]=1; } scanf("%s",s+1); m=strlen(s+1); for(int i=1;i<=m;i++) a[i]=F(s[i]); bool flag=0; for(int i=1;i<=4;i++) if(dfs(1,m,i)) printf("%c",DF(i)),flag=1; if(!flag) printf("The name is wrong!"); printf(" "); return 0; }