Solution

预处理f[i][j],代表第j列前i行的代价

枚举上下界,然后做最大子段和,g[i]代表选到第i列的代价,

　　g[k]=(g[k-1]<0?0:g[k-1])+f[j][k]-f[i-1][k]

复杂度O(n^3)

Notice

注意赋初值

// <2630.cpp> - Tue Oct 18 20:36:24 2016// This file is made by YJinpeng，created by XuYike's black technology automatically.// Copyright (C) 2016 ChangJun High School, Inc.// I don't know what this program is.#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int MAXN=410;int g[MAXN],f[MAXN][MAXN];int main(){    freopen("2630.in","r",stdin);    freopen("2630.out","w",stdout);    int n,m,ans=0;scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++){            char ch=getchar();            while(ch!='0'&&ch!='1')ch=getchar();            f[i][j]=f[i-1][j]+(ch=='0'?-1:1);        }    for(int i=1;i<=n;i++)        for(int j=i;j<=n;j++)            for(int k=1;k<=m;k++)                g[k]=(g[k-1]<0?0:g[k-1])+f[j][k]-f[i-1][k],ans=max(g[k],ans);    printf("%d\n",ans);    return 0;}