题目大意:给出n行m列01串,对于每一行所要花费的代价是行中第一个1和最后一个1之间的距离加一,现在你有魔法可以去除掉k个1,问去掉不多于k个1的情况下,你所能获得的最小代价是多少。

题解:
每一天翘多少课所得到的价值都是互相独立的,那么就很容易想到将每一天都看成一个物品组,翘不同数量的课可以达到不同的最大价值,然后跑分组背包即可。

但由于翘课顺序不同导致的剩余价值也不同,所以直接贪心递推地删点是不可取的

我们考虑搞一个辅助DP,设w[i][j]为第i天翘了j节课所达到的最大价值。

由于我们翘课只有从两边翘才可达到最优,那我们对于一个确定的j,可以分别枚举左右两边翘课的数量。

分好组后,跑01背包就可以了

#include <bits/stdc++.h>
#include <iostream>
#include <string.h>
#include <math.h>

using namespace std;
const int maxn = 505;
int a[maxn][maxn], L[maxn][maxn], R[maxn][maxn];
char str[maxn];
int w[maxn];
int dp[maxn][maxn], Lpost[maxn], Rpost[maxn];
int cnt[maxn];

/*
*/
int main() {
    int n, m, v, ans = 0;
//    freopen("in.in", "r", stdin);
    scanf("%d%d%d", &n, &m, &v);
    for (int i = 1; i <= n; i++) {
        scanf("%s", str + 1);
        for (int j = 1; j <= m; j++) {
            a[i][j] = str[j] - '0';
            L[i][j] = L[i][j - 1] + a[i][j];
            if (a[i][j]) Rpost[i] = j;
            cnt[i] += a[i][j];
        }
        for (int j = m; j >= 1; j--) {
            R[i][j] = R[i][j + 1] + a[i][j];
            if (a[i][j]) Lpost[i] = j;
        }
        if (cnt[i]) ans += Rpost[i] - Lpost[i] + 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= v; j++) dp[i][j] = dp[i - 1][j];
        memset(w, 0, sizeof(w));
        w[cnt[i]] = Rpost[i] - Lpost[i] + 1;
        for (int j = Lpost[i]; j <= Rpost[i]; j++) {
            for (int k = j + 1; k <= Rpost[i]; k++) {
                w[L[i][j] + R[i][k]] = max(w[L[i][j] + R[i][k]], Rpost[i] - k + 1 + j - Lpost[i] + 1);
                w[L[i][j - 1] + R[i][k]] = max(w[L[i][j - 1] + R[i][k]], j - Lpost[i] + Rpost[i] - k + 1);

                w[L[i][j] + R[i][k + 1]] = max(w[L[i][j] + R[i][k + 1]], j - Lpost[i] + 1 + Rpost[i] - k);
                w[L[i][j - 1] + R[i][k + 1]] = max(w[L[i][j - 1] + R[i][k + 1]], j - Lpost[i] + Rpost[i] - k);

                w[L[i][j]] = max(w[L[i][j]], j - Lpost[i] + 1);
                w[L[i][j - 1]] = max(w[L[i][j - 1]], j - Lpost[i]);
                w[R[i][k]] = max(w[R[i][k]], Rpost[i] - k + 1);
                w[R[i][k + 1]] = max(w[R[i][k + 1]], Rpost[i] - k);
            }
        }
        for (int j = 1; j <= v; j++) {
            for (int k = v; k >= j; k--) {
                dp[i][k] = max(dp[i][k], dp[i - 1][k - j] + w[j]);
            }
        }
    }
    printf("%d\n", ans - dp[n][v]);
    return 0;
}