codevs 1159 最大全0子矩阵 悬线法

题目

codevs 1159

题解

我开始看到这是道黄金题真没想到有多高深，不过学习了悬线法之后我才知道原来是2005年集训队论文里面的方法。（吃惊）。想了n多复杂的方法。 第一步，计算出cnt[i][j]表示(i,j)位置往上连续0的个数。然后如果对于每一行单独来看，答案为max{(k-j+1)* min{ cnt[i][j] , cnt[i][j+1] , … , cnt[i][k]}},枚举左右端点j,k，大意也就是因为这是个矩形所以是区间长*区间cnt最小值。这一步是正确的。如何快速得到这个答案呢。 本蒟蒻就想出了每一行需要n^2logn时间的方法，枚举端点，线段树维护最小值。其实这个方法只需要每行n^2，不过肯定会T 然后发现时间浪费在没有对上一行的信息加以利用。假如答案是有一维长度是cnt[i][j]，那么肯定会尽量往两边延伸使得第二维尽量大。所以我们想要维护一个l[i][j]和r[i][j]分别表示cnt[i][j]这个长度能向两边延伸的左右端点。 现在问题变为处理l,r数组。设原矩阵为mx。if(mx[i-1][j]==1) cnt[i][j]=1这时候的左右边界肯定为往两边延伸遇到的第一个1或者矩阵边界（设这个边界为L，R）。else cnt[i][j]=cnt[i-1][j]+1 这时候的左边界是max(l[i-1][j],L)稍微想一想就可以明白。右端点类似。所以现在处理出L,R即可，这个是非常简单的，扫一遍即可，不懂可以参照代码。

代码

//QWsin #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define rep(i) for(int i=1;i<=n;i++) #define per(i) for(int i=n;i>=1;i--) using namespace std; const int N=2000+10; inline int read() { char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); return ch=='1'; } int mx[N][N],cnt[N][N],l[N][N],r[N][N],ans; int L[N][N],R[N][N]; int main() { int n;cin>>n;; rep(i) rep(j) mx[i][j]=read(); rep(i) {int nowl=0;rep(j) if(mx[i][j])nowl=j;else L[i][j]=nowl+1;} rep(i) {int nowr=n+1;per(j) if(mx[i][j])nowr=j;else R[i][j]=nowr-1;} rep(i) rep(j) if(!mx[i][j]) { if(i==1||mx[i-1][j]) cnt[i][j]=1,l[i][j]=L[i][j],r[i][j]=R[i][j]; else cnt[i][j]=cnt[i-1][j]+1,l[i][j]=max(l[i-1][j],L[i][j]),r[i][j]=min(r[i-1][j],R[i][j]); } rep(i) rep(j) ans=max(ans,cnt[i][j]*(r[i][j]-l[i][j]+1)); cout<<ans; return 0; }