背包 DP【洛谷P4158】 [SCOI2009]粉刷匠

P4158 [SCOI2009]粉刷匠

windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。

windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。

如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？

一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

发现每一行都没有关系。

那么就是一个很显然的分组背包。

把每一行看成一个物品。

那么就需要预处理出来每一行刷i次合法的最大答案。

预处理用暴力DP就可以。

一定分析复杂度，先按暴力来。

code：

#include <iostream>

#include <cstdio>

#include <cstring>

#define debug puts("");

using namespace std;

const int wx=3017;

inline int read(){

	int sum=0,f=1; char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}

	return sum*f;

}

int n,m,t,num;

char c[wx],cc[wx][wx];

int zmj[wx],mm[wx],sum1[wx],sum2[wx];

int f[51][51][wx];

int F[wx];

void pre(){

	for(int i=1;i<=n;i++){

		scanf("%s",c+1);

		memset(sum1,0,sizeof sum1);

		memset(sum2,0,sizeof sum2);

		for(int j=1;j<=m;j++){

			if(c[j]=='1')sum1[j]=sum1[j-1]+1,sum2[j]=sum2[j-1];

			else sum2[j]=sum2[j-1]+1,sum1[j]=sum1[j-1];

		}

		for(int l=1;l<=min(t,m);l++)

			for(int j=1;j<=m;j++)

				for(int k=0;k<j;k++)

					f[i][j][l]=max(f[i][j][l],f[i][k][l-1]+max(sum1[j]-sum1[k],sum2[j]-sum2[k]));

	}

}

int main(){

	n=read(); m=read(); t=read(); pre();

	for(int i=1;i<=n;i++)

		for(int j=t;j>=0;j--)

			for(int k=1;k<=min(t,m);k++)

				if(j-k>=0)

					F[j]=max(F[j],F[j-k]+f[i][m][k]);

	printf("%d\n",F[t]);

	return 0;

}