url: https://www.luogu.com.cn/problem/P4158
tag:
动态规划，递推，枚举，背包DP
思路：
用 f[i][j] 表示前i块木板粉刷j次最多的正确次数。用 g[i][j][k] 表示第i块木板粉刷j次粉刷前k个格子时最多的正确次数。用 sum[i][j] 表示第i块木板，前j个格子中需要涂成蓝色的有几个。
所以可以知道状态转移方程为 f[i][j] = max(f[i][j], f[i - 1][j - k] + g[i][k][m]) ；
g[i][j][k] = max(g[i][j][k], g[i][j - 1][q] + max(sum[i][k] - sum[i][q], k - q - sum[i][k] + sum[i][q])) 最后遍历不同种粉刷次数中最多的粉刷格子数。
代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int f[51][2550], sum[51][2550];
int g[51][2550][51];
int n, m, t;
char s[100];
int main()
{
cin >> n >> m >> t;
for (int i = 1; i <= n; i ++)
{
cin >> s;
for (int j = 1; j <= m; j ++)
{
if (s[j - 1] == '1') sum[i][j] = sum[i][j - 1] + 1;
else sum[i][j] = sum[i][j - 1];
}
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
for (int k = 1; k <= m; k ++)
for (int q = j - 1; q < k; q ++)
g[i][j][k] = max(g[i][j][k], g[i][j - 1][q] + max(sum[i][k] - sum[i][q], k - q - sum[i][k] + sum[i][q]));
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= t; j ++)
for (int k = 0; k <= min(j, m); k ++)
f[i][j] = max(f[i][j], f[i - 1][j - k] + g[i][k][m]);
int res = 0;
for (int i = 1; i <= t; i ++) res = max(res, f[n][i]);
cout << res << endl;
return 0;
}