CF946D Timetable 动态规划

#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 = ‘\n‘) { ???????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 505int 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;}