Luogu-P4290-玩具取名

Posted on Edited on Word count in article: 715

题目 P4290 [HAOI2008] 玩具取名

题目描述

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

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

输入格式

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

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

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

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

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

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

输出格式

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

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

思路：区间dp

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

基本定义

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

  • dp[1][2][1]→truedp[1][2][1] \rightarrow true
  • dp[2][3][1]→truedp[2][3][1] \rightarrow true
  • dp[1][4][2]→truedp[1][4][2] \rightarrow true

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

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

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

状态

  • 初状态

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

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

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

    • 数字 ll 能变换为 [i,mid][i,mid]（dp[i][mid][l] == true）。
    • 数字 rr 能变换为 [mid+1,j][mid+1,j]（dp[mid + 1][j][r] == true）。
    • 数字 toto 能变换为 ll 和 rr（trans[to][l][r] == true）。

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

    1
    dp[i][j][to] |= dp[i][mid][l] && dp[mid + 1][j][r] && trans[to][l][r];

  • 末状态
    需要求的是整个字符串能不能由一个字母变换得到，即数字 i∈[1,4]i \in [1,4] 能否变换成 [1,s.length()][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;
}