先放题面

Description

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

Input

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

Output

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

Sample Input

3 6 3

111111

000000

001100

Sample Output

16

HINT

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

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

先简单说说自己最开始的wa解法：对所有木板直接dp，只能从该木板的长度内或其他木板的末尾转移过来。dp方程定义为：dp[k][i][j]表示刷k次、在第i个木板的第j格结束。结果后来对拍后才发现这个有后效性，挂了。

正解：

对每一个木板先进行一次dp，求出第i个木板刷k次最多能刷对多少格。然后再拿每个木板作为一个组，进行分组背包（其实将木板作为一个泛化物品进行背包问题会理解的更形象？）

然后有一个小小的优化：

在dp时，我们需要枚举之前的状态来选择最优解。而这一重枚举可能会造成超时（没试过），所以希望把它优化掉。用不着单调队列优化，将需枚举的量和在一起，每次取一个最值保存下来

就像这样：

f[k][i][j]=max(cnt[0][i][j]+tmp0,cnt[1][i][j]+tmp1);

tmp0=max(tmp0,f[k-1][i][j]-cnt[0][i][j]);

tmp1=max(tmp1,f[k-1][i][j]-cnt[1][i][j]);

完整代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

char c[55][55];

int n,m,T,cnt[2][55][55],f[3000][55][55],dp[3000][55];

int main(){

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

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

        scanf("%s",c[k]+1);

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

            cnt[0][k][i]=cnt[0][k][i-1]+(c[k][i]=='0');

            cnt[1][k][i]=cnt[1][k][i-1]+(c[k][i]=='1');

        }

    }

    int tmp0,tmp1;

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

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

            tmp0=tmp1=0;

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

                f[k][i][j]=max(cnt[0][i][j]+tmp0,cnt[1][i][j]+tmp1);

                tmp0=max(tmp0,f[k-1][i][j]-cnt[0][i][j]);

                tmp1=max(tmp1,f[k-1][i][j]-cnt[1][i][j]);

            }

        }

    }

    for(int k=1;k<=T;k++){

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

            dp[k][i]=max(dp[k][i],dp[k][i-1]);

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

                dp[k][i]=max(dp[k][i],dp[k-j][i-1]+f[j][i][m]);

        }

    }

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

    return 0;

}