【DP】BZOJ1296 [SCOI2009]粉刷匠

题面在这里

​

考虑每一行粉刷是独立的

对每一行DP：\(f_{i,j}\)表示前\(i\)个位置，刷了\(j\)个位置 \[ f_{i,j}=f_{k,j-1}+\max(num_0,num_1) \] 然后总的粉刷次数是确定的，把每行看作一个组，就是分组背包了

​

示例程序：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define cl(x,y) memset(x,y,sizeof(x))
using namespace std;

const int maxn=55,maxk=2505;
int n,m,K,N,s[maxn][maxn],f[maxn][maxk],g[maxn][maxk];
char a[maxn][maxn];
#define w(i,l,r) (max(s[i][r]-s[i][(l)-1],(r)-(l)+1-s[i][r]+s[i][(l)-1]))
#define up(x,y) (x=max(x,y))
int main(){
	scanf("%d%d%d",&n,&m,&K);
	for (int i=1;i<=n;i++) scanf("%s",a[i]+1);
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=m;j++)
	  s[i][j]=s[i][j-1]+a[i][j]-'0';
	for (int x=1;x<=n;x++){
		cl(f,192);
		f[0][0]=0;
		for (int i=1;i<=m;i++)
		 for (int j=1;j<=i&&j<=K;j++){
		 	f[i][j]=f[i-1][j];
		 	for (int k=0;k<i;k++)
		 	 up(f[i][j],f[k][j-1]+w(x,k+1,i));
		 }
		for (int i=1;i<=m;i++)
		 for (int j=i;j<=K;j++)
		  up(g[x][j],g[x-1][j-i]+f[m][i]);
	}
	int ans=0;
	for (int i=1;i<=K;i++) ans=max(ans,g[n][i]);
	printf("%d",ans);
	return 0;
}