bzoj1296 [SCOI2009]粉刷匠 DP

两次DP

第一次DP出每行前i个改j次的最优值

第二次DP出前i行改j次的最优值

#include<bits/stdc++.h>
using namespace std;
char s[55];
int sum[55];
int n,m,t;
int f[55][55],dp[55][2505];
int main(){
    scanf("%d%d%d",&n,&m,&t);
    for(int k=1;k<=n;k++){
        scanf("%s",s+1);
        memset(sum,0,sizeof sum);
        for(int i=1;i<=m;i++){
            sum[i]=sum[i-1]+s[i]-'0';
        }
        memset(f,0,sizeof f);
        for(int i=1;i<=m;i++)//前j个改i次 
            for(int j=1;j<=m;j++)
                for(int l=0;l<j;l++){//从l改到j 
                    int tmp=sum[j]-sum[l];
                    f[j][i]=max(f[j][i],f[l][i-1]+max(tmp,j-l-tmp));
                }
        for(int i=1;i<=t;i++){//前k行改i次的最优值 
            int tmp=min(i,m);
            for(int j=0;j<=tmp;j++){
                dp[k][i]=max(dp[k][i],dp[k-1][i-j]+f[m][j]);
            }
        }
    }
    int ans=-1;
    for(int i=1;i<=t;i++){
        ans=max(dp[n][i],ans);
    }
    printf("%d",ans);
    return 0;
}