Pagini recente » Cod sursa (job #1320588) | Cod sursa (job #2276411) | Cod sursa (job #1906518) | Cod sursa (job #1382035) | Cod sursa (job #2162813)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500;
char les[MAXN + 1][MAXN + 4];
int dp[MAXN + 2][MAXN + 2], aux[MAXN + 2][MAXN + 2], nb[MAXN + 2];
vector <int> v[MAXN + 2];
int main() {
// ifstream cin(".in");
// ofstream cout(".out");
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; ++i) {
cin >> (les[i] + 1);
for (int j = 1; j <= m; ++j) {
nb[i] += les[i][j] - '0';
if (les[i][j] == '1')
v[i].push_back(j);
}
}
memset(aux, 0x3f, sizeof aux);
for (int i = 1; i <= n; ++i) {
aux[i][nb[i]] = 0;
for (int j = nb[i] - 1; j >= 0; --j) {
int num = nb[i] - j;
int loc = INT_MAX;
for (int p = num - 1; p < (int) v[i].size(); ++p)
loc = min(loc, v[i][p] - v[i][p - num + 1] + 1);
aux[i][j] = loc;
}
for (int j = nb[i] + 1; j <= k; ++j)
aux[i][j] = 0;
}
memset(dp, 0x3f, sizeof dp);
for (int i = 0; i <= k; ++i)
dp[1][i] = aux[1][i];
for (int i = 2; i <= n; ++i)
for (int j = 0; j <= k; ++j) {
for (int num = 0; num <= k && num <= nb[i]; ++num)
dp[i][j] = min(dp[i][j], dp[i - 1][k - num] + aux[i][num]);
}
for (int i = 0; i < k; ++i)
dp[n][k] = min(dp[n][k], dp[n][i]);
cout << dp[n][k];
return 0;
}