题意

个长为 的 01 序列，可以涂色 次。一次涂色涂一个序列的某一段（连续），获得的分数为这一段中 0 或者 1 的个数。一个位置不能重复涂。求最大分数。

题解

对每一序列暴力 DP 即可，可以算出每一序列涂 次的答案。于是可以转化为一个背包问题。时间复杂度为 。

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m, t;
char s[55][55];
int lis[55], f[55][55];
int g[2505] = {0}, tmp[2505];
void init(){
    n = read(), m = read(), t = read();
    for (int i = 0; i < n; ++i) 
        scanf("%s", s[i]);  
}
void solve(){
    lis[0] = 0;
    for (int i = 0; i < n; ++i){
        int tot = 0;
        for (int j = 0; j < m; ){
            int k = j;
            while (k < m && s[i][j] == s[i][k])
                ++k;
            lis[++tot] = k - j;
            j = k; 
        }
        memset(f, 0, sizeof(f));
        for (int j = 1; j <= tot; ++j){
            int sm = 0;
            for (int k = j; k >= 1; --k){
                if ((j - k) % 2 == 0)
                    sm += lis[k];
                for (int l = k; l >= 1; --l)
                    f[j][l] = max(f[j][l], f[k - 1][l - 1] + sm);
            }
        }
        for (int j = 0; j <= t; ++j)
            tmp[j] = g[j];
        for (int w = 1; w <= tot; ++w){
            int maxi = 0;
            for (int j = w; j <= tot; ++j)
                maxi = max(maxi, f[j][w]);
            for (int j = w; j <= t; ++j)
                g[j] = max(g[j], tmp[j - w] + maxi);
        }
    }
    printf("%d\n", g[t]);
}
int main(){
    init();
    solve();
    return 0;
}