【每日一题】【5月6日】粉刷匠

题意：

块木板，每块木板有 个格子, 每个格子需要被涂上红色或者蓝色。
每次粉刷只能选择一块木板上的一段连续的格子，然后涂上一种颜色。
每个格子至多只能被粉刷一次。
问粉刷 次，正确粉刷的格子数最多是多少？

解法：

用 表示第 块木板粉刷 次，正确粉刷的格子总数。

在已经计算出 的前提下，剩下的就是一个分组背包问题：
用 表示总共粉刷了 次，正确粉刷的格子总数。

递推式为：

对应代码的第26~30行，注意循环顺序。
这部分复杂度为

然后再考虑如何计算 ：

对每块木板，定义 表示粉刷到第 个格子，共粉刷了 次的正确粉刷格子总数。

那么递推式为：

其中 表示前缀红色/蓝色的格子总数。

求 的复杂度为 。

求出 之后，就可以用来更新

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 50 + 5;
const int T = 2500 + 5;
int f[N][N], g[N][N], h[T], sum[2][N], n, m, t;
char s[N];
int main() {
    cin >> n >> m >> t;
    for(int i = 1; i <= n; i++) {
        memset(g, 0, sizeof g);
        memset(sum, 0, sizeof sum);
        cin >> s + 1;
        for(int j = 1; j <= m; j++) {
            sum[0][j] = sum[0][j - 1];
            sum[1][j] = sum[1][j - 1];
            sum[s[j] - '0'][j]++;
        }
        for(int j = 1; j <= m; j++) 
            for(int k = 1; k <= j; k++)
                for(int p = 0; p < j; p++) 
                    g[j][k] = max(g[j][k], g[p][k - 1] + max(sum[0][j] - sum[0][p], sum[1][j] - sum[1][p]));
        for(int j = 1; j <= m; j++) 
            for(int k = 1; k <= m; k++)
                f[i][j] = max(f[i][j], g[k][j]);
    }
    for(int i = 1; i <= n; i++) 
        for(int j = t; j >= 0; j--)
            for(int k = 1; k <= m; k++)
                if(j >= k)
                    h[j] = max(h[j], h[j - k] + f[i][k]);
    cout << h[t] << endl;
    return 0;
}