BZOJ 1296 粉刷匠

题意

n条木板，每条木板上有m个格子，每个格子有目标颜色0或1。一次可以粉刷连续若干格，每格只能被粉刷一次。T次粉刷后最多有多少格子颜色正确。（初始无颜色）

数据范围

$$n,m\leqslant50\ \ \ ;\ \ \ T\leqslant2500$$

题解

泛化背包很久以前就讲过，但一直没有练过，今天是第一次。
按照泛化背包的理解，每次先DP一行的状态，求出每一行粉刷i次的答案，再DP所有行的答案。

DP方程

f[i][j]表示当前行前i格粉刷j次的答案，f[i][j]=max{f[k][j-1]+v[k+1][i]}，其中v[k+1][i]表示粉刷一次k+1到i的格子最多有多少正确（预处理）。
g[i][j]表示前i行木板粉刷j次的答案，g[i][j]=max{g[i-1][k]+f[m][j-k]}。答案即为max{g[n][i]}。

代码

#include<cstdio>
int sum[60],f[60][2510],g[60][2510];
int MAX(int x,int y) {if (x>y) return x; return y;}
int main()
{
	int n,m,t,ans=0; char c[60];
	scanf("%d%d%d",&n,&m,&t);
	for (int k=1;k<=n;k++)
	{
		scanf("%s",c);
		for (int j=0;j<m;j++) sum[j+1]=sum[j]+(c[j]=='1');
		for (int i=1;i<=m;i++)
		for (int j=1;j<=t;j++)
		{
			f[i][j]=0;
			for (int l=0;l<i;l++)
			{
				int cnt=sum[i]-sum[l];
				f[i][j]=MAX(f[i][j],f[l][j-1]+MAX(cnt,i-l-cnt));
			}
		}
		for (int i=1;i<=t;i++)
		for (int j=0;j<=i;j++)
		g[k][i]=MAX(g[k][i],g[k-1][j]+f[m][i-j]);
	}
	for (int i=0;i<=t;i++) ans=MAX(ans,g[n][i]);
	printf("%d",ans);
	return 0;
}