【BZOJ1296】【SCOI2009】粉刷匠

先dp处理出每行刷\(i\)次能够正确粉刷多少个格子

然后背包

// <1296.cpp> - 08/30/16 19:43:46
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
bool gc(){
    char ch=getchar();
    while(ch!='1'&&ch!='0')ch=getchar();
    return ch=='1'; 
}
const int MAXN=100001;
const int INF=1e9;
int a[60],dp[60][2600],pp[60][2600];
int main(){
    int n=gi(),m=gi(),T=gi();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[j]=a[j-1]+gc();
            for(int k=1;k<=T;k++){
                dp[j][k]=dp[j-1][k];
                for(int l=0;l<j;l++)dp[j][k]=max(dp[j][k],dp[l][k-1]+max(a[j]-a[l],j-l-a[j]+a[l]));
            }
        }
        for(int k=1;k<=T;k++)pp[i][k]=pp[i-1][k];
        for(int k=1;k<=T;k++)
            for(int j=k;j<=T;j++)pp[i][j]=max(pp[i][j],pp[i-1][j-k]+dp[m][k]);
    }
    printf("%d",pp[n][T]);
    return 0;
}

// <1296.cpp> - 08/30/16 19:43:46

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

bool gc(){

char ch=getchar();

while(ch!='1'&&ch!='0')ch=getchar();

return ch=='1';

}

const int MAXN=100001;

const int INF=1e9;

int a[60],dp[60][2600],pp[60][2600];

int main(){

int n=gi(),m=gi(),T=gi();

for(int i=1;i<=n;i++){

for(int j=1;j<=m;j++){

a[j]=a[j-1]+gc();

for(int k=1;k<=T;k++){

dp[j][k]=dp[j-1][k];

for(int l=0;l<j;l++)dp[j][k]=max(dp[j][k],dp[l][k-1]+max(a[j]-a[l],j-l-a[j]+a[l]));

}

for(int k=1;k<=T;k++)pp[i][k]=pp[i-1][k];

for(int k=1;k<=T;k++)

for(int j=k;j<=T;j++)pp[i][j]=max(pp[i][j],pp[i-1][j-k]+dp[m][k]);

}

printf("%d",pp[n][T]);

return 0;

}