题目链接
题解
f[l][r][k]表示l-r能否合成字母k
由枚举自己可能的分解转移得到
记忆化搜索好写些
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}
while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();
return x * f;
}
const int maxn = 17;
const int maxm = 207;
int mp[maxm];
char is[maxn] = {'W','I','N','G'};
int ID[5];
char a[5][maxm][2],t[maxm];
int f[maxm][maxm][maxn];
bool dp (int l,int r,int k) {
if(l == r) return t[l] == is[k];
int & ret = f[l][r][k];
if(ret != -1) return ret;
for(int i = 1;i <= ID[k];++ i)
for(int j = l;j <= r - 1;++ j)
if( dp(l,j,mp[a[k][i][0]]) && dp(j + 1,r,mp[a[k][i][1]]))
return ret = 1;
return ret = 0;
}
int main() {
memset(f,-1,sizeof f);
for(int i = 0;i < 4;++ i) ID[i] = read();
for(int i = 0;i < 4;++ i)
for(int j = 1;j <= ID[i];++ j) scanf("%s",a[i][j]);
scanf("%s",t + 1);
mp['W'] = 0,mp['I'] = 1,mp['N'] = 2,mp['G'] = 3;
int len = strlen(t + 1); bool flag = 0;
for(int i = 0;i < 4;++ i)
if(dp(1,len,i)) printf("%c",is[i]),flag = 1;
if(! flag)puts("The name is wrong!");
return 0;
}