题解 P4290 【[HAOI2008]玩具取名】

览遍千秋 · 2018-08-01 18:29:43 · 题解

Update Log

• 2025-02-10：修改题解格式与代码，使得其符合现行题解标准，并自己审核通过。

这是一道区间动规题。

考虑将字母抽象为数值，即 WING 分别对应 1,2,3,4。

用 ok[a][b][c] 表示第 c 个字母是否可以变成第 a 个字母和第 b 个字母的组合。

设 dp[l][r][c] 表示区间 [l,r] 能否最终变成第 c 个字母。

在区间动态规划中，通常将区间长度作为动态规划的阶段。即，通常先完成小区间答案的计算，再以此来计算大区间的答案。

字符串的当度为 L，从小到大枚举区间长度 len 与区间左端点 l，可以计算出区间右端点 r=l+len-1。

区间 [l,r] 可以由其中的两个子区间转化而来。枚举 k(l \le k < r)，将区间 [l,r] 切分为区间 [l,k],[k+1,r]。

当存在一个 k 满足 \begin{cases}dp[l][k][a] \text{ is true}\\ dp[k+1][r][b] \text{ is true} \\ ok[a][b][c] \text{ is true}\end{cases} 时，dp[l][r][c] 为 true。其中，1 \le a,b,c \le 4，需要枚举。

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 200 + 7;

bool dp[MAXN][MAXN][5], ok[5][5][5];
int W, I, N, G, L;
int num[MAXN];
string S;

int char2int(char c) {
    switch(c) {
        case 'W': return 1;
        case 'I': return 2;
        case 'N': return 3;
        case 'G': return 4;
    }
    return 0;
}

void record(char a, char b, int type) {
    int aid = char2int(a), bid = char2int(b);
    ok[aid][bid][type]=1;
}

int main() {
    cin >> W >> I >> N >> G;
    for(int i = 1; i <= W; i++) {
        char a, b;
        cin >> a >> b;
        record(a, b, 1);
    }
    for(int i = 1; i <= I; i++) {
        char a, b;
        cin >> a >> b;
        record(a, b, 2);
    }
    for(int i = 1; i <= N; i++) {
        char a, b;
        cin >> a >> b;
        record(a, b, 3);
    }
    for(int i = 1; i <= G; i++) {
        char a, b;
        cin >> a >> b;
        record(a, b, 4);
    }
    cin >> S; L = (int)S.size();
    for(int i = 0; i < L; i++) {
        num[i + 1] = char2int(S[i]);
    }
    for(int i = 1; i <= L; i++) {
        dp[i][i][num[i]] = 1;
    }

    for(int len = 2; len <= L; len++) {
        for(int l = 1; l + len - 1 <= L; l++) {
            int r = l + len - 1;
            for(int k = l; k < r; k++) {
                for(int a = 1; a <= 4; a++) {
                    if(!dp[l][k][a]) continue;
                    for(int b = 1; b <= 4; b++) {
                        if(!dp[k + 1][r][b]) continue;
                        for(int c = 1; c <= 4; c++) {
                            if(ok[a][b][c] && dp[l][k][a] && dp[k + 1][r][b]) {
                                dp[l][r][c] = true;
                            }
                        }
                    }
                }
            }
        }
    }

    bool flag = false;

    if(dp[1][L][1]) printf("W"), flag = true;
    if(dp[1][L][2]) printf("I"), flag = true;
    if(dp[1][L][3]) printf("N"), flag = true;
    if(dp[1][L][4]) printf("G"), flag = true;
    if(flag)
        printf("\n");
    else
        printf("The name is wrong!\n");
    return 0;
}