题解 P4158 【[SCOI2009]粉刷匠】

夏夜空 · 2018-09-20 14:01:48 · 题解

好容易做出这一题。题解里面大佬的代码都太高深看不懂，这里给个清新的

#include<cstdio>
inline int max(int a,int b){return a>b?a:b;} 
int n,m,t,ans;
const int N=61;
char s[N];
int sum[N],f[N][N],g[N][2333];
//sum[i]表示从开始到i的'1'总数 
//f[i][j]表示(枚举的当前行)前i个格子刷j次获得的最大分数
//g[i][j]表示前i行刷j次获得的最大分数
int main() {
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1; i<=n; i++) {
        scanf("%s",s+1);
        for(int j=1; j<=m; j++) sum[j]=sum[j-1]+(s[j]=='1');
            for(int k=1; k<=m; k++) {
        for(int j=1; j<=m; j++) {
                f[j][k]=0;//初始化 
                for(int p=0; p<j; p++){
                    int x=max((j-sum[j])-(p-sum[p]),sum[j]-sum[p]);//如果刷(p+1)~j这节,刷1好还是刷0好 
                    f[j][k]=max(f[j][k],f[p][k-1]+x);//刷(p+1)~j好,还是不刷好 
                }
            }
        }
        for(int j=1; j<=t; j++)//枚举刷的次数 
            for(int k=1; k<=j&&k<=m; k++)
                g[i][j]=max(g[i][j],g[i-1][j-k]+f[m][k]);
                //比较当前情况好,还是(前一行少刷k次的最好情况)加上(刷现在这一行刷k次的最好情况)好 
    }
    for(int i=1; i<=t; i++) ans=max(ans,g[n][i]);//找出刷前m行刷i次的最大分数 
    printf("%d",ans);
}