题意

windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。
windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。
如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？
一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。
数据范围：
100%的数据，满足 1 <= N,M <= 50 ； 0 <= T <= 2500 。

分析

这是一道比较明显的 题？
记 表示第 行刷了 次的最大值，接下来就是一个简单的分组背包问题了。
现在就是要求 。
由于每一行是独立的，于是我们每一行单独求。
现在的问题就转化为：每一行有 个数，粉刷 次，能正确刷的最多格子数。
这个又是一个简单 了啊。
记 表示前 个数，粉刷了 次的最大格子数。然后枚举上一次粉刷的位置 ，将 到 都粉刷为一种颜色。记 为 的前缀和。
那么转移方程：

（全涂蓝）

（全涂红）

总的复杂度是

代码如下

#include <bits/stdc++.h>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define N 55
using namespace __gnu_pbds;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
struct custom_hash {
       static uint64_t splitmix64(uint64_t x) {
           x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int ksm(int a, int b, int p){
    int s = 1;
    while(b){
        if(b & 1) s = z * s * a % p;
        a = z * a * a % p;
        b >>= 1;
    }
    return s;
}
int f[N][N], v[N][N], g[N * N], a[N], s[N];
int main(){
    int i, j, n, m, k, T, t;
    n = read(); m = read(); T = read();
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++) scanf("%1d", &a[j]), s[j] = s[j - 1] + a[j];
        memset(f, 0, sizeof(f));
        for(j = 1; j <= m; j++){
            for(k = 1; k <= m; k++){
                for(t = 0; t < j; t++){
                    f[j][k] = max(f[j][k], f[t][k - 1] + s[j] - s[t]);
                    f[j][k] = max(f[j][k], f[t][k - 1] + (j - t) - (s[j] - s[t]));
                }
            }
        }
        for(j = 0; j <= m; j++) v[i][j] = f[m][j];
    }
    for(i = 1; i <= n; i++){
        for(j = T; j >= 0; j--){
            for(k = 1; k <= m; k++) if(j >= k)
                g[j] = max(g[j], g[j - k] + v[i][k]);
        }
    }
    printf("%d", g[T]);
    return 0;
}