Bzoj 1055: [HAOI2008]玩具取名 (区间DP)

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1055

区间动态规划和可达性DP的好题.

开始WA了几次,感到非常奇怪.

原因竟然是n被定义了char型,真是zz了.

\(f[i][j][k]\)表示区间\(i\)到\(j\)可以由\(k\)这个字符是否可以转变过来.

转移的时候枚举中间点转移就好了.

#include <iostream>

#include <cstring>

#include <cstdio>

const int maxN = 200 + 7;

using namespace std;

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

bool f[maxN][maxN][5];

bool is_match[5][5][5];

int q[5];

char s[maxN],c[5];

inline int pd(char i){

    if(i == Q[1]) return 1;

    if(i == Q[2]) return 2;

    if(i == Q[3]) return 3;

    if(i == Q[4]) return 4;

}  

int main() {

    for(int i = 1;i <= 4;++ i)

        scanf("%d",&q[i]);

    for(int i = 1;i <= 4;++ i) {

        for(int j = 1;j <= q[i];++ j) {

            scanf("%s",c);

            is_match[i][pd(c[0])][pd(c[1])] = true;

        }

    }

    scanf("%s",s + 1);

    int n = strlen(s + 1);

    for(int i = 1;i <= n;++ i)

        f[i][i][pd(s[i])] = true;

    for(int leg = 1;leg < n;++ leg) {

        for(int l = 1;l + leg <= n;++ l) {

        	int r = l + leg;

        	for(int k = l;k < r;++ k) {

        		for(int i = 1;i <= 4;++ i) { //枚举 l 到 r 的字符

        			for(int j = 1;j <= 4;++ j) {// 枚举l 到 k 的字符

        				for(int a = 1;a <= 4;++ a) { //枚举k + 1到r的字符

        					if(is_match[i][j][a]) {

        						if( f[l][k][j] && f[k + 1][r][a])

        							f[l][r][i] = 1;

							}

        				}

        			}

        		}

        	}

        }

    }

    bool flag = false;

    for(int i = 1;i <= 4;++ i)

        if(f[1][n][i]) flag = true,printf("%c",Q[i]);

    if(!flag) puts("The name is wrong!");

    return 0;

}

巴特西

Bzoj 1055: [HAOI2008]玩具取名 (区间DP)

Bzoj 1055: [HAOI2008]玩具取名 (区间DP)

最新文章

热门文章