[SCOI2009]粉刷匠

题目描述

\(windy\)有 \(N\) 条木板需要被粉刷。每条木板被分为 \(M\) 个格子。每个格子要被刷成红色或蓝色。

\(windy\)每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。每个格子最多只能被粉刷一次。

如果\(windy\)只能粉刷 \(T\) 次，他最多能正确粉刷多少格子？

一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

输入输出格式

输入格式：

第一行包含三个整数，\(N ,M, T\)。

接下来有N行，每行一个长度为\(M\)的字符串，'\(0\)'表示红色，'\(1\)'表示蓝色。

输出格式：

包含一个整数，最多能正确粉刷的格子数。

输入输出样例

输入样例#1：

输出样例#1：

说明

\(30\%\)的数据，满足 \(1 <= N,M <= 10 ； 0 <= T <= 100\) 。

\(100\%\)的数据，满足 \(1 <= N,M <= 50 ； 0 <= T <= 2500\) 。

题解

\(dp[i][j][k]\)表示第\(i\)块板已经刷完了前\(j\)块用了\(k\)次的最大价值；

我们会发现每个\(i\)都是独立的，所以转移时不去看\(i\)，把转移想成每个独立的子问题。

\(dp[i][j][k]\)的转移：

我们可以枚举一个断点\(h\)，使用一次粉刷机会从\(h+1\)到\(j\)，价值为\(h+1\)到\(j\)的\(max(red+bule)\)。

\(dp[i][j][k]=max(dp[i][j][k],dp[i][h][k-1]+mx[i][h+1][j])\);

\(mx[i][l][r]\)为提前预处理第\(i\)块板\(l\)到\(r\)的 \(max(red+bule)\)。

最后直接跑分组背包统计答案。

code：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cctype>

#define N 55

#define R register

#define ll long long

using namespace std;

template<typename T>inline void read(R T &a){

    R char c=getchar();R T x=0,f=1;

    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}

    a=f*x;

}

int n,m,t,ans;

int dp[N][N][N],sum[2][N],mx[N][N][N],f[2505];

char s[N];

int main(){

    read(n);read(m);read(t);

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

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

        sum[0][0]=sum[1][0]=0;

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

            sum[0][j]=sum[0][j-1]+(s[j]=='0');

            sum[1][j]=sum[1][j-1]+(s[j]=='1');

        }

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

            mx[i][j][j]=1;

            for(R int k=j+1;k<=m;k++)

                mx[i][j][k]=max(sum[0][k]-sum[0][j-1],sum[1][k]-sum[1][j-1]);

        }

    }

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

        for(R int j=1;j<=m;j++)

            for(R int k=1;k<=m;k++)

                for(R int h=0;h<j;h++)

                    dp[i][j][k]=max(dp[i][j][k],dp[i][h][k-1]+mx[i][h+1][j]);

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

        for(R int j=t;j>=0;j--)

            for(R int k=0;k<=m;k++)

                if(j-k>=0)f[j]=max(f[j],f[j-k]+dp[i][m][k]),ans=max(ans,f[j]);

    printf("%d\n",ans);

    return 0;

}

粉刷

【BZOJ1296】[SCOI2009]粉刷匠 （DP+背包）