946D. Timetable

#include <map>#include <cstdio>#include <cstring>#include <algorithm>#define INF 0x3f3f3f3fusing namespace std;const int maxn = 1e6 + 10;int n, m, k;int A[510];int cst[510][510];int dp[510][510];int main() { ???memset(cst, INF, sizeof(cst)); ???memset(dp, INF, sizeof(dp)); ???scanf("%d%d%d", &n, &m, &k); ???for (int i = 1; i <= n; i++) { ???????A[0] = 0; ???????int tmp; ???????for (int j = 1; j <= m; j++) { ???????????scanf("%1d", &tmp); ???????????if (tmp == 1) { ???????????????A[++A[0]] = j; ???????????} ???????} ???????cst[i][0] = A[0] == 0 ? 0 : A[A[0]] - A[1] + 1; ???????for (int j = 1; j < A[0]; j++) { ???????????for (int kk = 1; kk <= j + 1; kk++) { ???????????????cst[i][j] = min(cst[i][j], A[A[0] - (j - kk + 1)] - A[kk] + 1); ???????????} ???????} ???????for (int j = A[0]; j <= k; j++) cst[i][j] = 0; ???} ???dp[0][0] = 0; ???for (int i = 1; i <= n; i++) { ???????for (int j = 0; j <= k; j++) { ???????????for (int kk = 0; kk <= j; kk++) { ???????????????dp[i][j] = min(dp[i][j], dp[i - 1][j - kk] + cst[i][kk]); ???????????} ???????????????????????} ???} ???printf("%d\n", dp[n][k]); ???return 0;}