[SCOI2009]粉刷匠

DP 背包

题面

戳我

解析

在每一行$DP$处理出$f[i][j]$。
（到第$i$个位置，这一次刷的是第$i$个位置的颜色，这一行刷了$j$次时，这一行最多刷对了多少块砖）
这个从同行前面转移过来就行。
然后合并信息，得出每一行刷$j$次最多能刷对多少块。
最后对所有的行进行多重背包$DP$就行。
复杂度$O(n^4)$。

唯一可能要注意的就是$DP$数组的初始化。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=55,mod=1e9+7;
int n,m,T,a[N],f[N][N],b[N][N],dp[N][N*N];
char s[N];
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=gi();m=gi();T=gi();
    fp(i,1,n)
    {
        scanf("%s",s+1);
        fp(j,1,m) a[j]=a[j-1]+(s[j]=='1');
        memset(f,-63,sizeof(f));f[0][0]=0;
    fp(j,1,m)
          fp(k,1,j)
            fp(l,0,j-1)
            f[j][k]=max(f[j][k],f[l][k-1]+((s[j]=='1')?(a[j]-a[l]):(j-l-(a[j]-a[l]))));
        fp(j,1,m)
          fp(k,0,j)
            b[i][k]=max(b[i][k],f[j][k]);
    }
    memset(dp,-63,sizeof(dp));
    dp[0][T]=0;
    fp(i,1,n)
        fp(j,0,T)
        fp(k,0,j)
    {
        dp[i][j-k]=max(dp[i][j-k],dp[i-1][j]+b[i][k]);
        dp[i][j]=max(dp[i][j],dp[i-1][j]);
    }
    printf("%d\n",dp[n][0]);
  return 0;
}