bzoj1296

题解：

简单ｄｐ

先每一行的列ｄｐ一下

然后行的ｄｐ一下

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int n,m,T,f[N],g[N],cost[N][N],dp[N][N*N];
char s[N][N];
int main()
{
    scanf("%d%d%d",&n,&m,&T);
    for (int i=1;i<=n;i++)scanf("%s",s[i]+1);
    for (int i=1;i<=n;i++)
     {
         for (int j=1;j<=m;j++)
          {
              f[j]=f[j-1];
              g[j]=g[j-1];
              if (s[i][j]=='1')f[j]++;
              else g[j]++;
          }
         memset(cost,0,sizeof cost);
         for (int j=1;j<=m;j++)
          for (int k=1;k<=j;k++)
           for (int l=1;l<=j;l++)
            cost[j][k]=max(cost[j][k],cost[l-1][k-1]+max(f[j]-f[l-1],g[j]-g[l-1]));
        for (int j=1;j<=T;j++)
         for (int k=1;k<=m&&k<=j;k++)
          dp[i][j]=max(dp[i][j],dp[i-1][j-k]+cost[m][k]);
     }
    printf("%d",dp[n][T]); 
}