[HAOI 2008] 玩具取名

题目大意

给定一个由 WWIINNGG 组成的字符串,并给出一些形如「XYXY 可由 ZZ 替代」的规则,最终将字符串化为一个字符,求可能的字符(题目中涉及到的字符均只有 WWIINNGG 四个),否则输出 The name is wrong!

1S2001 \leqslant |S| \leqslant 200

1W,  I,  N,  G161 \leqslant W,\; I,\; N,\; G \leqslant 16

题目链接

【HAOI 2008】玩具取名 - Luogu 4290

题解

暴力的区间 DP。

f(l,  r,  c)f(l, \; r, \; c) 表示区间 [l,  r][l, \; r] 是否能被字符 cc 替代,用六层循环暴力地枚举进行 DP。。。(分别枚举区间长、区间起点、区间划分为两个的划分点、左区间的字符、右区间的字符、合并的字符)

代码

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
#include <cstdio>
#include <cstring>
const int MAXN = 205;
const int CHAR_SET = 4;
bool f[MAXN][MAXN][CHAR_SET], trans[CHAR_SET][CHAR_SET][CHAR_SET];
int getID(char c) {
if (c == 'W') return 0;
if (c == 'I') return 1;
if (c == 'N') return 2;
if (c == 'G') return 3;
}
static char s[MAXN];
void dp(int n) {
for (int i = 1; i <= n; i++) f[i][i][getID(s[i])] = true;
for (int l = 2; l <= n; l++) for (int s = 1; s + l - 1 <= n; s++) {
int t = s + l - 1;
for (int k = s; k < t; k++) {
for (int cl = 0; cl < 4; cl++) if (f[s][k][cl]) {
for (int cr = 0; cr < 4; cr++) if (f[k + 1][t][cr]) {
for (int c = 0; c < 4; c++) if (trans[cl][cr][c]) f[s][t][c] = true;
}
}
}
}
}
int main() {
int W, I, N, G;
scanf("%d %d %d %d", &W, &I, &N, &G);
for (int i = 0; i < W; i++) {
char s[2];
scanf("%s", s);
trans[getID(s[0])][getID(s[1])][0] = true;
}
for (int i = 0; i < I; i++) {
char s[2];
scanf("%s", s);
trans[getID(s[0])][getID(s[1])][1] = true;
}
for (int i = 0; i < N; i++) {
char s[2];
scanf("%s", s);
trans[getID(s[0])][getID(s[1])][2] = true;
}
for (int i = 0; i < G; i++) {
char s[2];
scanf("%s", s);
trans[getID(s[0])][getID(s[1])][3] = true;
}
scanf("%s", s + 1);
int n = strlen(s + 1);
dp(n);
bool ok = false;
char ch[5] = "WING";
for (int c = 0; c < 4; c++) if (f[1][n][c]) ok = true, putchar(ch[c]);
puts(ok ? "" : "The name is wrong!");
return 0;
}