粉刷匠

题意

n个木板，每个木板分成m块，每块只能刷一次，每次只能刷一块木板的连续的若干块。指定每块的颜色（总共只有两种），问刷t次最多有几块刷成指定颜色。

思路

想了好久，老往区间dp想，没想出合适的状态表示和转移就滚去看题解了。看完题解容(shang)易(mian)想(xie)到(zhe) 用 表示第i个木板刷j次前k个刷对的个数。显然, 其中 是第i块到第j块刷一次最多能刷对的个数。之后就是一个裸的分组背包，容量为刷的次数，第i组对应体积为i的物品价值为。

代码

#include<bits/stdc++.h>
using namespace std;

int n, m, t;
int pre[55], dp[55][55][55], f[2550];
char s[55];

int main()
{
    cin >> n >> m >> t;
    for(int i = 0; i < n; i++){
        scanf("%s", s + 1);
        for(int j = 1; j <= m; j++){
            pre[j] = pre[j - 1] + (s[j] == '1');
        }

        for(int j = 1; j <= m; j++){
            for(int k = 1; k <= m; k++){
                for(int l = j - 1; l < k; l++){
                    int tem = pre[k] - pre[l];
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][l] + max(tem, k - l - tem));
                }
            }
        }
    }

    for(int i = 0; i < n; i++){
        for(int k = t; k > 0; k--){
            for(int j = 1; j <= min(k, m); j++){
                f[k] = max(f[k], f[k - j] + dp[i][j][m]);
                //cout << "k = " << k << " "<<f[k];
            }
        }
    }
    cout << f[t] << endl;

    return 0;   
}