题目链接（洛谷）
题目大意
某人想给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后喜好，将名字中任意一个字母用“WING”中的某些两个字母代替，使得名字能够扩充。
现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。
给出每个字母可以用哪些种两个字母代替。输出该名字可能由哪些字母变形而得到。如果给的名字不能由任何一个字母变形而得到则输出"The name is wrong!”
名字长度\(\le 200\)，每个字母可以替换的字母对数\(\le 16\)
分析
反着想，可以理解为：给出一字母序，按规则将连续字母合并成一个字母，最后看可以合并成哪一个单字母。
先定义\(dp(l,r)\)为区间\([l,r]\)的答案，发现区间不一定只对应一个字母。所以再添加一维：
设\(dp(i,j,ch)\)表示在区间\([l,r]\)中是否可以合并出\(ch\)这个字母。
转移：
设\(cl\)和\(cr\)分别为\(ch\)可以变成的某一双字符的左右字符，枚举子区间
\(dp(i,j,ch) |=(dp(i,k,cl) \& dp(k+1,j,cr))\)
初始化：\(dp[i][i][s[i]] = true\) ，\(s\)为输入的字符串。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include<bits/stdc++.h>
using namespace std;
inline int ren(char ch){
if(ch=='W') return 1;
if(ch=='I') return 2;
if(ch=='N') return 3;
if(ch=='G') return 4;
}
struct node{
int l,r;
};
char s[205];
int sl,len[5];
bool dp[205][205][5];
node r[5][1000];
int main(){
cin>>len[1]>>len[2]>>len[3]>>len[4];
for(int i=1;i<=4;i++){
for(int j=1;j<=len[i];j++){
char ch;
cin>>ch,r[i][j].l=ren(ch);
cin>>ch,r[i][j].r=ren(ch);
}
}
cin>>s+1;
sl=strlen(s+1);
for(int i=1;i<=sl;i++) dp[i][i][ren(s[i])]=true;
for(int l=1;l<=sl;l++){
for(int i=1;i+l-1<=sl;i++){
int j=i+l-1;
for(int k=i;k<=j;k++){
for(int ch=1;ch<=4;ch++){
if(dp[i][j][ch]) continue;
for(int ind=1;ind<=len[ch];ind++){
dp[i][j][ch]|=(dp[i][k][r[ch][ind].l]&dp[k+1][j][r[ch][ind].r]);
}
}
}
}
}
bool bo=false;
if(dp[1][sl][1]) cout<<"W",bo=true;
if(dp[1][sl][2]) cout<<"I",bo=true;
if(dp[1][sl][3]) cout<<"N",bo=true;
if(dp[1][sl][4]) cout<<"G",bo=true;
if(!bo) cout<<"The name is wrong!";
return 0;
}
|