Luogu-P4290-玩具取名

Posted on Edited on Word count in article: 1.1k

题目 P4290 [HAOI2008] 玩具取名

题目描述

某人有一套玩具，并想法给玩具命名。首先他选择 W, I, N, G 四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用 W, I, N, G 中任意两个字母代替，使得自己的名字能够扩充得很长。

现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。

输入格式

第一行四个整数 $W, I, N, G$。表示每一个字母能由几种两个字母所替代。

接下来 $W$ 行，每行两个字母,表示 W 可以用这两个字母替代。

接下来 $I$ 行，每行两个字母，表示 I 可以用这两个字母替代。

接下来 $N$ 行，每行两个字母，表示 N 可以用这两个字母替代。

接下来 $G$ 行，每行两个字母，表示 G 可以用这两个字母替代。

最后一行一个长度不超过 $L$ 的字符串。表示这个玩具的名字。

输出格式

一行字符串，该名字可能由哪些字母变形而得到。（按照 W, I, N, G 的顺序输出）

如果给的名字不能由任何一个字母变形而得到则输出 The name is wrong!。

思路：区间dp

区间dp的时间复杂度为 $O(n^3)$，本题数据范围较小，可用！
将题中的 $W,I,N,G$ 分别对应数字 $1,2,3,4$。

基本定义

设 $dp[i][j][k]$ 表示 $i \sim j$ 的区间（从 $1$ 开始）是否能由 $k$ 对应的字母（下文简称为数字 $k$）变换得到。
对于样例 $1$：

  • $dp[1][2][1] \rightarrow true$
  • $dp[2][3][1] \rightarrow true$
  • $dp[1][4][2] \rightarrow true$

设 $trans[i][j][k]$ 表示 $i$ 对应的字母能变换成 $j,k$ 对应的两个字母。

设 $m[c]$ 表示字母 $c$ 对应的数字，$s$ 代表给定的名字（字符串）。

1
2
3
4
m['W'] = 1;
m['I'] = 2;
m['N'] = 3;
m['G'] = 4;

状态

  • 初状态

因为每一个字母显然能由自己“变换”得到，所以对于第 $i$ 个位置（从 $1$ 开始）：

1
dp[i][i][m[s[i - 1]]] = true;

  • 状态转移方程
    如果在 $[i,j]$ 内恰好能由一个数字 $to$ 变换得到，需要同时满足以下条件（$\exists mid \in [i,j)$）：

  • 数字 $l$ 能变换为 $[i,mid]$（dp[i][mid][l] == true）。

  • 数字 $r$ 能变换为 $[mid+1,j]$（dp[mid + 1][j][r] == true）。

  • 数字 $to$ 能变换为 $l$ 和 $r$（trans[to][l][r] == true）。

所以，状态转移方程如下：

1
dp[i][j][to] |= dp[i][mid][l] && dp[mid + 1][j][r] && trans[to][l][r];
  • 末状态
    需要求的是整个字符串能不能由一个字母变换得到，即数字 $i \in [1,4]$ 能否变换成 $[1, s.length()]$ 内的字符串。
1
if(dp[1][s.length()][i]) cout << letters[i];

同时，如果没有任何一个数字能使该条件成立，也要输出"The name is wrong!"。

1
2
3
4
5
6
7
8
9
10
bool flag = false;
for(int i = 1; i <= 4; i++) {
    if(dp[1][s.length()][i]) {
        cout << letters[i];
         flag = true;
    }
}
if(!flag) {
    cout << "The name is wrong!";
}

AC Code

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
67
68
// template v7
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int inf = 0x7f7f7f7f;

const int N = 201;
const int M = 70;

bool dp[N][N][5];

bool trans[5][5][5];

// WING -> 1234
int num[5];

char letters[] = {' ', 'W', 'I', 'N', 'G'};

int m[100];

int main() {
    // freopen("test.in", "r", stdin);
    m['W'] = 1;
    m['I'] = 2;
    m['N'] = 3;
    m['G'] = 4;
    for(int i = 1; i <= 4; i++) {
        cin >> num[i];
    }
    char c1, c2;
    for(int i = 1; i <= 4; i++) {
        for(int j = 0; j < num[i]; j++) {
            cin >> c1 >> c2;
            trans[i][m[c1]][m[c2]] = true;
        }
    }
    string s;
    cin >> s;
    for(int i = 1; i <= s.length(); i++) {
        dp[i][i][m[s[i - 1]]] = true;
    }
    for(int len = 2; len <= s.length(); len++)
        // 3 characters, len = 2, start i: 1 ~ 2, end i: 2 ~ 3
        for(int i = 1; i <= s.length() - len + 1; i++) {
            int j = i + len - 1;
            for(int mid = i; mid < j; mid++)
                // i~mid, mid+1~j => i~j
                for(int l = 1; l <= 4; l++)
                    for(int r = 1; r <= 4; r++)
                        for(int to = 1; to <= 4; to++)
                            dp[i][j][to] |= dp[i][mid][l] && dp[mid + 1][j][r] && trans[to][l][r];
        }

    bool flag = false;
    for(int i = 1; i <= 4; i++) {
        if(dp[1][s.length()][i]) {
            cout << letters[i];
            flag = true;
        }
    }
    if(!flag) {
        cout << "The name is wrong!";
    }
    cout << endl;
    return 0;
}