预处理出每一行去掉$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 = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', c = gc();
return p * w;
}
int wr[], rw;
#define pc(iw) putchar(iw)
tpr inline void write(ra o, char c = '\n') {
if(!o) pc('');
if(o < ) o = -o, pc('-');
while(o) wr[++ rw] = o % , o /= ;
while(rw) pc(wr[rw --] + '');
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, : ; }
tpr inline bool ckmax(ra &a, ra b) { return (a < b) ? a = b, : ; }
}
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, , n) {
memset(pre, , sizeof(pre));
memset(suf, , sizeof(suf));
rep(l, , m) pre[l] = pre[l - ] + (s[i][l] == '');
drep(l, m, ) suf[l] = suf[l + ] + (s[i][l] == '');
if(pre[m] == ) continue; memset(f[i], , sizeof(f[i]));
rep(l, , m) rep(r, l, m)
if(s[i][l] == '' && s[i][r] == '')
cmin(f[i][pre[l - ] + suf[r + ]], r - l + );
rep(j, pre[m], k) f[i][j] = ;
}
} inline void DP() {
memset(g, , sizeof(g));
g[][] = ;
rep(i, , n) {
rep(i1, , k) rep(i2, , k)
if(i1 + i2 <= k) cmin(g[i][i1 + i2], g[i - ][i1] + f[i][i2]);
}
int ans = 2e9;
rep(i, , k) cmin(ans, g[n][i]);
write(ans);
} int main() {
n = read(); m = read(); k = read();
rep(i, , n) scanf("%s", s[i] + );
Pre(); DP();
return ;
}