「SCOI 2009」粉刷匠

题目大意：

预处理出 $f[i][j]$ 表示第 $i$ 块木板粉刷 $j$ 次最多可以符合要求的方块数，然后01背包合并这 $n$ 块木板即可。

对于第一层DP，设 $g[i][j]$ 表示当前这块木板的前 $i$ 个格子粉刷 $j$ 次最多可以符合要求的方块数，有

$$g[i][k] = \max\{g[j][k-1] + \max(w[j+1][i], b[j+1][i])\} (0 \leq j < i)$$

其中 $j$ 表示上一次粉刷截止的位置，$w[i][j],b[i][j]$ 分别表示区间 $[i,j]$ 的白色/黑色方格数。

#include <cstdio>
#include <cstring>
 
const int N = 55, M = 2505;
int n, m, t, w[N], b[N], f[N][M], g[N][M]; char s[N];
 
int max(int x, int y) {
    return x > y ? x : y;
}
 
int main() {
    scanf("%d%d%d", &n, &m, &t);
    for (int cur = 1; cur <= n; ++cur) {
        scanf("%s", s + 1);
        for (int i = 1; i <= m; ++i) {
            w[i] = w[i-1], b[i] = b[i-1];
            if (s[i] == '0') ++w[i]; else ++b[i];
        }
        for (int i = 1; i <= m; ++i) //前i个格子
            for (int j = 1; j <= t; ++j) { //粉刷j次
                g[i][j] = g[i-1][j];
                for (int k = j - 1; k < i; ++k) //上一次截止的位置
                    g[i][j] = max(g[i][j], g[k][j-1] + max(w[i]-w[k], b[i]-b[k]));
            }
        for (int i = 1; i <= t; ++i) f[cur][i] = g[m][i];
        memset(g, 0, sizeof g);
    }
    for (int i = 1; i <= n; ++i) //前i块木板
        for (int j = 1; j <= t; ++j) { //粉刷了j次
            g[i][j] = g[i-1][j];
            for (int k = 1; k <= j; ++k) //第i块木板粉刷了k次
                g[i][j] = max(g[i][j], g[i-1][j-k] + f[i][k]);
        }
    printf("%d\n", g[n][t]);
    return 0;
}