「BZOJ1055」[HAOI2008]玩具取名

Description

某人有一套玩具,并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后
他会根据自己的喜好,将名字中任意一个字母用WING中任意两个字母代替,使得自己的名字能够扩充得很长。
现在,他想请你猜猜某一个很长的名字,最初可能是由哪几个字母变形过来的。

Input

第一行四个整数WWIINNGG。表示每一个字母能由几种两个字母所替代。接下来WW行,每行两个字母,表示WW
以用这两个字母替代。接下来II行,每行两个字母,表示II可以用这两个字母替代。接下来NN行,每行两个字母,表示NN
可以用这两个字母替代。接下来GG行,每行两个字母,表示GG可以用这两个字母替代。最后一行一个长度不超过LenLen
字符串。表示这个玩具的名字。

Output

一行字符串,该名字可能由哪些字母变形而得到。(按照WING的顺序输出)如果给的名字不能由任何一个字母
变形而得到则输出The name is wrong!

Sample Input

1
2
3
4
5
6
1 1 1 1
II
WW
WW
IG
IIII

Sample Output

1
IN

HINT

W可以变成II所以IIII可以缩成WW IN均能变成WW所以WW又可以缩成I或者N 所以最终答案应该按照WING的顺序
100%100\%数据满足Len200Len\leq 200WWIINNG16G\leq 16

Solution

fi,j,kf_{i,j,k}表示区间[i,j][i,j]能否变成字符kk
oki,j,kok_{i,j,k}表示字符kk能否由字符iijj合并得到。
转移一下就行了。
注意:可以不去替换的,所以fi,i,si=1f_{i,i,s_i}=1

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

int ok[5][5][5];
bool f[210][210][5];
int m[5];
char tmp[6];
int n;
char s[310];
char ans[] = "WING";
int id[666];
int main() {
id['W'] = 0;
id['I'] = 1;
id['N'] = 2;
id['G'] = 3;
for(int i = 0; i < 4; ++i)
m[i] = read();
for(int i = 0; i < 4; ++i) {
for(int j = 1; j <= m[i]; ++j) {
scanf("%s", tmp);
ok[id[tmp[0]]][id[tmp[1]]][i] = 1;
}
}
scanf("%s",s+1);
n = strlen(s + 1);
for(int i = 1; i < n; ++i) for(int j = 0; j < 4; ++j) if(ok[id[s[i]]][id[s[i + 1]]][j]) f[i][i + 1][j] = 1;
for(int i = 1; i <= n; ++i) f[i][i][id[s[i]]] = 1;
for(int len = 3; len <= n; ++len) {
for(int i = 1; i + len - 1 <= n; ++i) {
int j = i + len - 1;
for(int k = i; k < j; ++k) {
for(int z = 0; z < 4; ++z) if(!f[i][j][z])
for(int x = 0; x < 4; ++x) if(f[i][k][x])
for(int y = 0; y < 4; ++y) if(f[k + 1][j][y])
if(ok[x][y][z])
f[i][j][z] = 1;
}
}
}
bool ok = 0;
for(int i = 0; i < 4; ++i)
if(f[1][n][i]) putchar(ans[i]), ok = 1;
if(!ok) {
puts("The name is wrong!");
return 0;
}
puts("");
return 0;
}