题目描述

输入

输出

样例输入

3 2

4 0

-10 8

-2 -2

样例输出

4

数据范围

解法

枚举两条扫描线，在这两条扫描线之间的矩阵，可以将之转化为一个序列b[i]=a[i][1..m]。

然后矩阵上的问题就转化成序列上的问题：

给定一个序列，求最长的连续子序列的和为正数的长度。

---

考虑到是所有区间问题，考虑分治。

对于一个区间[l,r]，要求的是跨两半部分的最长长度。

先求出以mid为右端点的最长子区间；

设一个指针指向mid，考虑右移指针。

如果新加入元素是小于0，那么答案不会更优，左指针肯定要右移至少一位才会使得答案平衡；

如果新加入元素大于0，那么考虑把左指针一直左移直到合法子区间极大。

由于左指针至多左移2∗n，时间复杂度为O(nlogn)。

---

总的时间复杂度为O(n3logn)。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long long#define ln(x,y) ll(log(x)/log(y))#define sqr(x) ((x)*(x))using namespace std;const char* fin="max.in";const char* fout="max.out";const ll inf=0x7fffffff;const ll maxn=307;ll n,m,i,j,k,ans;ll a[maxn][maxn],b[maxn],sum[maxn][maxn];ll solve(ll l,ll r){    ll i=0,j=0,k=0,y=0,mid=(l+r)/2,tmp,tmd=0;    if (l==r) return b[l]>0?1:0;    tmp=max(solve(l,mid),solve(mid+1,r));    k=y=0;    for (i=mid;i>=l;i--){        k+=b[i];        if (k>0) tmd=mid-i+1,y=k;    }    tmp=max(tmp,tmd);    j=mid-tmd+1;    i=k=0;    for (i=mid+1;i<=r;i++){        k+=b[i];        if (b[i]>0){            while (j>l && k+y+b[j-1]>0) y+=b[--j];        }else if (b[i]==0){        }else if (j
          
           0) tmp=max(tmp,i-j+1); } return tmp;}int main(){ freopen(fin,"r",stdin); freopen(fout,"w",stdout); scanf("%lld%lld",&n,&m); for (i=1;i<=n;i++) for (j=1;j<=m;j++) scanf("%lld",&a[i][j]),sum[i][j]=a[i][j]+sum[i][j-1]; for (i=1;i<=m;i++) for (j=i;j<=m;j++){ for (k=1;k<=n;k++) b[k]=sum[k][j]-sum[k][i-1]; ans=max(ans,solve(1,n)*(j-i+1)); } printf("%lld",ans); return 0;}
          
         
        
       
      
     

启发

当要处理子矩阵问题时，可以用两条扫描线把问题转化到序列上。

处理所有区间问题可以考虑分治。