预处理出每一行去掉$k$个1能获得的最小代价
之后做一次分组背包$dp$即可
预处理可以选择暴力枚举区间...
复杂度$O(n^3)$
#include <set> #include <map> #include <queue> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> namespace remoon { #define re register #define ri register int #define ll long long #define tpr template <typename ra> #define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++) #define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --) #define gc getchar inline int read() { int p = 0, w = 1; char c = gc(); while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); } while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc(); return p * w; } int wr[50], rw; #define pc(iw) putchar(iw) tpr inline void write(ra o, char c = ' ') { if(!o) pc('0'); if(o < 0) o = -o, pc('-'); while(o) wr[++ rw] = o % 10, o /= 10; while(rw) pc(wr[rw --] + '0'); pc(c); } tpr inline void cmin(ra &a, ra b) { if(a > b) a = b; } tpr inline void cmax(ra &a, ra b) { if(a < b) a = b; } tpr inline bool ckmin(ra &a, ra b) { return (a > b) ? a = b, 1 : 0; } tpr inline bool ckmax(ra &a, ra b) { return (a < b) ? a = b, 1 : 0; } } using namespace std; using namespace remoon;
#define sid 505 int n, m, k; char s[sid][sid]; int pre[sid], suf[sid]; int f[sid][sid], g[sid][sid]; inline void Pre() { rep(i, 1, n) { memset(pre, 0, sizeof(pre)); memset(suf, 0, sizeof(suf)); rep(l, 1, m) pre[l] = pre[l - 1] + (s[i][l] == '1'); drep(l, m, 1) suf[l] = suf[l + 1] + (s[i][l] == '1'); if(pre[m] == 0) continue; memset(f[i], 56, sizeof(f[i])); rep(l, 1, m) rep(r, l, m) if(s[i][l] == '1' && s[i][r] == '1') cmin(f[i][pre[l - 1] + suf[r + 1]], r - l + 1); rep(j, pre[m], k) f[i][j] = 0; } } inline void DP() { memset(g, 56, sizeof(g)); g[0][0] = 0; rep(i, 1, n) { rep(i1, 0, k) rep(i2, 0, k) if(i1 + i2 <= k) cmin(g[i][i1 + i2], g[i - 1][i1] + f[i][i2]); } int ans = 2e9; rep(i, 0, k) cmin(ans, g[n][i]); write(ans); } int main() { n = read(); m = read(); k = read(); rep(i, 1, n) scanf("%s", s[i] + 1); Pre(); DP(); return 0; }