分组背包dp

$O(NMT)$

C++ 代码

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

const int N = 55, M = 2505;

char g[N];

int w[N][N], s[N], f[M], n, m, T;

int main(){
    scanf("%d %d %d", &n, &m, &T);

    // 将每条木板看作一组, 采用分组背包的思想

    while(n--){
        memset(w, 0, sizeof(w));
        memset(s, 0, sizeof(s));
        scanf("%s", g + 1);

        for(int i = 1; i <= m; i++) s[i] = s[i - 1] + g[i] - '0';

        // w[i][j] 表示在此条木板的前i个格子粉刷j次能正确粉刷的格子数
        // 由于不能重复粉刷, 因此需要枚举上一步已经粉刷到的位置

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= i; j++){
                for(int k = 0; k < i; k++){
                    int bule = s[i] - s[k];
                    int red = i - k - bule;
                    w[i][j] = max(w[i][j], w[k][j - 1] + max(bule, red));    
                    }
                }
            }


        for(int j = T; j >= 0; j--){
            for(int k = 1; k <= m; k++){    // 枚举该组的粉刷次数
                if(j - k >= 0) f[j] = max(f[j], f[j - k] + w[m][k]);
                }
            }
        }

    printf("%d\n", f[T]);
    return 0;
}