解题思路

二维dp+三维dp：参考题解

这个题目难入手就难在是多块木板，二维的情况。
我们试试康把维度降低，如果单看当前处理的这块木板，通过一个三维的 表示第i块木板，粉刷了j次，涂了前面k个格子的正确格子数。
对应一个木板，只存在红蓝两种颜色，在输入数据时，通过处理前缀和，可以得知某个位置前某种颜色格子数。
假设前缀和记录蓝色，sum[k] - sum[l]表示[l,k]的蓝色格子；
k - l - (sum[k] - sum[l])表示[l,k]的红色格子数。
那么对于每块木板得到三维状态转移方程
截取l这个决策点位置涂到状态k，取涂 蓝色 or 红色 的最大值即可。
那么处理得到了上面这个三维的f数组，对于二维的木板填涂方法来说。
前面i - 1块木板涂 j - k次，剩余的k交给第i块木板涂满m个格子

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43655815&returnHomeType=1&uid=919749006

Code

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 55;
const int M = 2505;
ll dp[N][M];    // dp[i][j]   前i个木板粉刷j次的正确格子数
ll f[N][M][N]; // f[i][j][k] 第i个木板粉刷j次涂了前面k个格子的正确格子数
ll sum[N][N]; // sum[i][j] 第i个木板第j个木板前蓝色格子的数目
char s[N];

int main() {
    int n = read(), m = read(), t = read();
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s + 1);
        for (int j = 1; j <= m; ++j)
            sum[i][j] = sum[i][j - 1] + (s[j] == '1');
    }
    for (int i = 1; i <= n; ++i) //第i块木板
        for (int j = 1; j <= m; ++j)
            for (int k = 1; k <= m; ++k)
                for (int l = j - 1; l < k; ++l)
                    //在[l,k]中选红色或者蓝色多的一种颜色涂起来
                    f[i][j][k] = max(f[i][j][k], f[i][j - 1][l] + max(sum[i][k] - sum[i][l], k - l - sum[i][k] + sum[i][l]));
    ll ans = 0;
    for (int i = 1; i <= n; ++i) //状态
        for (int j = 1; j <= t; ++j) { //阶段
            for (int k = 0; k <= min(j, m); ++k) { //决策
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + f[i][k][m]);
            }
            ans = max(ans, dp[i][j]);
        }
    printf("%lld\n", ans);
    return 0;
}

// 16MS