自动搬运

查看原文

来自洛谷，原作者为

	7wwwwth i am flesh and i am bone.

搬运于2025-08-24 21:57:08，当前版本为作者最后更新于2018-08-13 17:23:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

明显是一个dp

定义一个 f[i][j]的数组来表示前i条木板粉刷j次的情况下能正确粉刷的最大格子数

定义一个g[i][j][k]来表示第i条木板上粉刷j次涂了前k个格子的情况下能正确粉刷的最大格子数

用sum数组来记录蓝色格子数 某个区间的格子数减去蓝色格子数就是粉色格子数（用前缀和来记录）

要是求最大的格子数 那么就要求一个m使得

  f[i][j]=max(f[i][j],f[i-1][j-k]+g[i][k][m])

用一个区间来想

接下来就是求g[i][j][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]));

其中sum[i][k]-sum[i][q]蓝色格子

k-q-sum[i][k]+sum[i][q]该段的粉色格子

最后看看粉刷多少次时有最大的f[i][j]记作ans；

愉快地输出吧！

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int f[51][2550],sum[51][2550];
int g[51][2550][51];
int n,m,t;
char s[150];

int main(){
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++){
		cin>>s;
		sum[i][0]=0;
		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 ans=0;
	for(int i=1;i<=t;i++) ans=max(ans,f[n][i]);
	cout<<ans;
	
}