题目大意:给出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; }