【题解】LuoGu4158：粉刷匠

最新推荐文章于 2021-12-14 21:57:03 发布

丰川样子小孩姐

最新推荐文章于 2021-12-14 21:57:03 发布

阅读量277

点赞数 1

分类专栏：题解 LuoGu DP 文章标签：题解 LuoGu DP

本文链接：https://blog.csdn.net/ModestCoder_/article/details/108298417

版权

题解同时被 3 个专栏收录

435 篇文章

订阅专栏

LuoGu

255 篇文章

订阅专栏

125 篇文章

订阅专栏

本文深入探讨了动态规划(DP)算法在解决特定问题中的应用，通过实例详细讲解了状态定义、状态转移方程及代码实现，为读者提供了一个全面理解DP算法的视角。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

原题传送门
很好的一个dp
令 $f_{i,j}$ 表示前 $i$ 行刷了 $j$ 次的答案， $g_{i,j,k}$ 表示第 $i$ 行前 $k$ 个，刷了 $j$ 次的最大价值

$f_{i,j}=max(f_{i-1,j-k}+g_{i,k,m})$
$g_{i,j,k}=max(g_{i,j-1,l}+max(sum_{i,k}-sum_{i,l},(k-l)-(sum_{i,k}-sum_{i,l})))$

COde：

#include <bits/stdc++.h>
#define maxn 60
#define maxm 2510
using namespace std;
int n, m, t, f[maxn][maxm], g[maxn][maxn][maxn], sum[maxn][maxn];
char s[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

int main(){
	scanf("%d%d%d", &n, &m, &t);
	for (int i = 1; i <= n; ++i){
		scanf("%s", s + 1);
		for (int j = 1; j <= m; ++j) sum[i][j] = sum[i][j - 1] + (s[j] == '1') ;
	}
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= min(m, t); ++j)
			for (int k = 1; k <= m; ++k)
				for (int l = j - 1; l < k; ++l)
					g[i][j][k] = max(g[i][j][k], g[i][j - 1][l] + max(sum[i][k] - sum[i][l], k - l - sum[i][k] + sum[i][l]));
	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 ans = 0;
	for (int i = 0; i <= t; ++i) ans = max(ans, f[n][i]);
	printf("%d\n", ans);
	return 0;
}