题解：P4158 [SCOI2009] 粉刷匠

先考虑总体上的思考方向：

• 首先发现木板之间独立，可以任意分配其 达到不同的 。
• 假设我们已知对于木板 的最优策略 ，表示在该木板前 的位置粉刷 次达到的最大匹配；
• 此时可以把木板 看成 类物品，其中代价为 的价值就只用考虑所有 策略中最赚的一个，即为 ；
• 这就是普普通通的背包板子了，相信大家都会；

关键就在于怎么处理出 数组：

• 注意到数据量很小，可以枚举每次粉刷的区间左右端点 ；
• 对于每个 ，考虑分配 次，从 位置转移过来，增加的价值就是区间内一的个数或者零的个数，取赚的那一种；

几个细节：

1. 处理 数组的时候， 的情况是要考虑的，这代表着对于这个点单独刷一下的情况；
2. 统计答案和背包的时候都要考虑粉刷 次的情况；
3. 可以使用滚动数组，但是没有必要，如果觉得脑袋像我一样不好用的可以选择同样不去优化这个空间；

代码：

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 55;
const int MAXT = 2505;

int n, m, t;

string str;
int oneCnt[MAXN];
int f[MAXN][MAXT];
int g[MAXN][MAXT];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m >> t;

    for (int i = 1; i <= n; ++i) {
        memset(oneCnt, 0, sizeof(oneCnt));
        memset(g, 0, sizeof(g));

        cin >> str;
        str = " " + str;
        for (int tot = 1; tot <= m; ++tot)
            oneCnt[tot] = oneCnt[tot - 1] + (str[tot] == '1');
        for (int r = 1; r <= m; ++r)
            for (int cost = 1; cost <= t; ++cost)
                for (int l = 1; l <= r; ++l) {
                    int one = oneCnt[r] - oneCnt[l - 1];
                    g[r][cost] = max(g[r][cost], g[l - 1][cost - 1] + one);
                    g[r][cost] = max(g[r][cost], g[l - 1][cost - 1] + (r - l + 1 - one));
                }
        for (int tot = 0; tot <= t; ++tot)
            for (int cost = tot; cost <= t; ++cost)
                f[i][cost] = max(f[i][cost], f[i - 1][tot] + g[m][cost - tot]);
    }

    int ans = 0;
    for (int i = 0; i <= t; ++i)
        ans = max(ans, f[n][i]);
    cout << ans;
    return 0;
}