题目链接：

 

题目分析

这种类似区间 DP 的记忆化搜索都是很相近的，比如字符串压缩和字符串扩展都差不多。

都是将现在 Solve 的区间分成子区间，再求解子区间。

这道题 Solve(l, r, x) 求能否将 [l, r] 的区间还原成 x ，那么就将它分成两段，看是否能左段变成 p ， 右段变成 q。 （x 能变成 pq）

 

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int MaxL = 200 + 5;char Ch[5] = {'W', 'I', 'N', 'G'};int len;int n[5], f[MaxL][MaxL][5];char S[MaxL];bool Tr[5][5][5];int Solve(int l, int r, int x) { if (f[l][r][x] != 0) return f[l][r][x]; if (l == r) { if (S[l] == Ch[x]) { f[l][r][x] = 1; return 1; } else { f[l][r][x] = -1; return -1; } } for (int i = l; i <= r - 1; ++i) { for (int j = 0; j < 4; ++j) { for (int k = 0; k < 4; ++k) { if (!Tr[x][j][k]) continue; if (Solve(l, i, j) == 1 && Solve(i + 1, r, k) == 1) { f[l][r][x] = 1; return 1; } } } } f[l][r][x] = -1; return -1;}int GetNum(char c) { for (int i = 0; i < 4; ++i) if (c == Ch[i]) return i; return -1;}int main() { for (int i = 0; i < 4; ++i) scanf("%d", &n[i]); char cc[3]; for (int i = 0; i < 4; ++i) { for (int j = 1; j <= n[i]; ++j) { scanf("%s", cc); Tr[i][GetNum(cc[0])][GetNum(cc[1])] = true; } } scanf("%s", S + 1); len = strlen(S + 1); bool Flag = false; for (int i = 0; i < 4; ++i) if (Solve(1, len, i) == 1) { printf("%c", Ch[i]); Flag = true; } if (!Flag) printf("The name is wrong!"); printf("\n"); return 0;}