Codevs 1744 格子染色==BZOJ 1296 粉刷匠

1744 格子染色

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题解

查看运行结果

题目描述 Description

有 n 条木板需要被粉刷。每条木板被分为 m 个格子。每个格子要被刷成红
色或蓝色。

输入描述 Input Description

Dizzy 每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。每个
格子最多只能被粉刷一次。如果 Dizzy 只能粉刷 t 次，他最多能正确粉刷多少格
子？一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

输出描述 Output Description

第一行包含三个整数，n m t。接下来有n行，每行一个长度为m的字符串，'0'表
示红色，'1'表示蓝色。

样例输入 Sample Input

3 6 3
111111
000000
001100

样例输出 Sample Output

数据范围及提示 Data Size & Hint

1 ≤ n,m ≤ 50 ； 0 ≤ t ≤ 2500 。

分类标签 Tags 点此展开

动态规划

题解：

稍微复杂一点的划分dp

设f[i][j][k]为第i行前j个k次粉刷正确的最大值

由于每行循环使用，可以去掉第一维，但每次不要忘了清零（WA了好久）

f[j][k]=max{ f[u][j-1] + max(u+1到j的蓝色的个数，u+1到j的红颜色的个数) }

设h[i][k]为第i行分成k份的最大值

h[i][k]=f[i][m][k]

设dp[i][k]为前i行总共分成k份的最大值

dp[i][k]=dp[i-1][t-x]+h[i][x]

x表示在第i行使用x次

AC代码：

#include<cstdio>

#include<algorithm>

using namespace std;

#define N 51

#define M 2501

int n,m,t,s1[N][N],s2[N][N],f[N][N],h[N][N],dp[N][M];

char str[N];

inline int sum1(int i,int l,int r){

    return s1[i][r]-s1[i][l-];

}

inline int sum2(int i,int l,int r){

    return s2[i][r]-s2[i][l-];

}

int main(){

    scanf("%d%d%d",&n,&m,&t);

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

        scanf("%s",str+);

        for(int j=;j<=m;j++){

            s1[i][j]=s1[i][j-];

            s2[i][j]=s2[i][j-];

            str[j]==''?s1[i][j]++:s2[i][j]++;

        }

    }

    for(int i=;i<=n;i++){//行

        for(int j=;j<=m;j++){//前j个数

            for(int k=;k<=min(t,j);k++){//分成k份

                f[j][k]=;//注意f是每行重复使用的，需要清零！

                for(int u=k-;u<=j-;u++){//分割点

                    f[j][k]=max(f[j][k],f[u][k-]+max(sum1(i,u+,j),sum2(i,u+,j)));

                }

            }

        }

        for(int k=;k<=min(t,m);k++){

            h[i][k]=f[m][k];

        }

    }

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

        for(int k=;k<=t;k++){

            for(int x=;x<=k;x++){

                dp[i][k]=max(dp[i][k],dp[i-][k-x]+h[i][x]);

            }

        }

    }

    printf("%d",dp[n][t]);

    return ;

}

巴特西

Codevs 1744 格子染色==BZOJ 1296 粉刷匠

1744 格子染色

分类标签 Tags 点此展开

最新文章

热门文章