题目
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;
}