BZOJ 1296: [SCOI2009]粉刷匠

對于每一行f[i][j]表示前i列刷j次最多刷對的格子數

易得f[i][j]=max(f[i][j],   max{f[k][j-1]+max(cnt[i]-cnt[k],i-k-(cnt[i]-cnt[k]))}   ) cnt[i]表示前i個中的1的數量(或0的數量)

然後對每一行是一個分組，對總體做一次分組背包就好了

#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,t;
int f[55][55],g[55][55],cnt[55],f1[2500];

int main()
{
	scanf("%d %d %d",&n,&m,&t);
	for(int i=1;i<=n;++i)
	{
		char ch[55];
		scanf("%s",ch);
		for(int j=1;j<=m;++j)
		{
			int x=ch[j-1]-'0';
//			printf("%d",x);
			cnt[j]=cnt[j-1]+(x==1);
		}
//		printf("\n");
		for(int j=1;j<=m;++j)
			for(int p=1;p<=m;++p)
			{
				f[p][j]=0;
				for(int k=0;k<p;++k)
					f[p][j]=max(f[p][j],f[k][j-1]+max(cnt[p]-cnt[k],p-k-(cnt[p]-cnt[k])));
			}
		for(int j=0;j<=m;++j) g[i][j]=f[m][j];
	}
	for(int i=1;i<=n;++i)
		for(int j=t;j>=0;--j)
			for(int k=0;k<=min(m,j);++k) f1[j]=max(f1[j],f1[j-k]+g[i][k]);
	printf("%d",f1[t]);
	return 0;
}
           

一開始以為可以豎着塗還可以重複塗，以為又隻能打開題解了，還好多看了一會兒題，不然就錯過了一次獨立切題的機會了