BZOJ1296 [SCOI2009]粉刷匠【dp】

题目

windy有 N 条木板需要被粉刷。每条木板被分为 M 个格子。每个格子要被刷成红色或蓝色。 windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。每个格子最多只能被粉刷一次。如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

输入格式

输入文件paint.in第一行包含三个整数，N M T。接下来有N行，每行一个长度为M的字符串，’0’表示红色，’1’表示蓝色。

输出格式

输出文件paint.out包含一个整数，最多能正确粉刷的格子数。

输入样例

3 6 3

111111

000000

001100

输出样例

提示

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

题解

将每一行做一次O(M3)动归，求出每行刷k次下做多的收益

设f[i][j]表示当前行前i个刷j次的最大收益

f[i][j]=max(f[k][j−1]+max(sum1(k,j),sum0(k,j)))

得出了每行刷1、2、3……K次的收益，总共可以刷T次，就可以做一个分组背包

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u]; k != -1; k = ed[k].nxt)

using namespace std;

const int maxn = 60,maxm = 2505,INF = 1000000000;

int f[maxn][maxm],g[maxn][maxn],N,M,T,sum[maxn];

char s[maxn];

int main(){

    scanf("%d%d%d",&N,&M,&T);

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

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

        for (int j = 1; j <= M; j++) sum[j] = sum[j - 1] + (s[j] == '1');

        for (int k = 1; k <= M; k++)

            for (int j = 1; j <= M; j++){

                g[j][k] = 0;

                for (int l = 0; l < j; l++)

                    g[j][k] = max(g[j][k],g[l][k - 1] + max(sum[j] - sum[l],j - l - (sum[j] - sum[l])));

            }

        for (int j = 1; j <= T; j++)

            for (int k = 1,t = min(j,M); k <= t; k++)

                f[i][j] = max(f[i][j],f[i - 1][j - k] + g[M][k]);

    }

    int ans = 0;

    REP(i,T) ans = max(ans,f[N][i]);

    printf("%d",ans);

    return 0;

}

粉刷