bzoj 1296 DP

/**************************************************************

    Problem: 1296

    User: BLADEVIL

    Language: C++

    Result: Accepted

    Time:120 ms

    Memory:1564 kb

****************************************************************/

 

//By BLADEVIL

#include <cstdio>

#include <cstring>

#include <algorithm>

#define maxn 60

#define maxk 3000

 

using namespace std;

 

int n,m,t,ans;

int map[maxn][maxn],w[maxn][maxn],sum[maxn][maxn],W[maxn][maxn],ww[maxn][maxk];

char s[maxn];

 

int work(int x) {

    memset(w,0,sizeof w);

    memset(sum,0,sizeof sum);

    for (int i=1;i<=m;i++)

        for (int j=i;j<=m;j++)

            for (int k=i;k<=j;k++)

                if (map[x][k]) sum[i][j]++;

    for (int i=1;i<=m;i++)

        for (int j=i;j<=m;j++) sum[i][j]=max(sum[i][j],j-i+1-sum[i][j]);//printf("%d %d %d
",i,j,sum[i][j]);

    for (int i=1;i<=m;i++) 

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

            w[j][i]=w[j-1][i];

            for (int k=0;k<j;k++) 

                w[j][i]=max(w[j][i],w[k][i-1]+sum[k+1][j]);

        }

    for (int i=1;i<=m;i++) W[x][i]=w[m][i];//printf("%d ",W[x][i]); printf("
");

}

 

int main() {

    scanf("%d %d %d",&n,&m,&t);

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

        scanf("%s",s);

        for (int j=0;j<m;j++) map[i][j+1]=(s[j]=='1')?1:0;

    }

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

    for (int i=1;i<=t;i++) 

        for (int j=1;j<=n;j++)

            for (int k=0;k<=min(m,i);k++)

                ww[j][i]=max(ww[j][i],ww[j-1][i-k]+W[j][k]),ans=max(ans,ww[j][i]);

    printf("%d
",ans);

    return 0;

}