洛谷 P4290 [HAOI2008]玩具取名

传送门

思路

博客半年没更新了，来更新个博文吧

在\(dsr\)聚聚博客的帮助下，我用半个上午和一个中午的时间苟延残喘地完成了这道题

先是读题目读大半天，最后连个样例都看不懂

之后又是想思路，实在想不出来，便去看了\(dsr\)学长的博客，发现是一道区间\(DP\)题

我们用\(f[i][j][k]\)来表示\(i\)、\(j\)这个区间能否压缩成为\(k\)这个字符

基本框架为

枚举长度len
    枚举起点i
        计算终点j
        枚举中点k
            起点到中点的check
                中点到终点的check
                    转移

字符不多，所以是可以跑过去的

代码

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;

inline int read() {
    char c = getchar();
    int x = 0, f = 1;
    for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
    return x * f;
}

int le[5], f[211][211][5];
bool z[5][5][5], flag;
char yuan[5], s[5], ss[211];

int calc(char w) {
    if(w == 'W') return 1;
    if(w == 'I') return 2;
    if(w == 'N') return 3;
    if(w == 'G') return 4;
}

int main() {
    strcpy(yuan, " WING");
    for(int i = 1; i <= 4; i++) le[i] = read();
    for(int i = 1; i <= 4; i++) {
        for(int j = 1; j <= le[i]; j++) {
            scanf("%s", &s);
            z[i][calc(s[0])][calc(s[1])] = 1;
        }
    }
    scanf("%s", ss + 1);
    int n = strlen(ss + 1);
    for(int i = 1; i <= n; i++) f[i][i][calc(ss[i])] = 1;
    for(int len = 1; len < n; len++) {//枚举长度
        for(int i = 1; i <= n; i++) {//枚举起点
            int j = i + len;
            if(j > n) break;//终点
            for(int k = i; k < j; k++) {//中点
                for(int ip = 1; ip <= 4; ip++) {
                    if(f[i][k][ip]) {
                        for(int jp = 1; jp <= 4; jp++) {
                            if(f[k + 1][j][jp]) {
                                for(int kp = 1; kp <= 4; kp++) {
                                    if(z[kp][ip][jp] == 1) {
                                        f[i][j][kp] = 1;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    for(int i = 1; i <= 4; i++) {
        if(f[1][n][i]) {
            flag = 1;
            printf("%c", yuan[i]);
        }
    }
    if(!flag) cout << "The name is wrong!\n";
    return 0;
}