写一道CODEVS的题目
其实我还是很喜欢CODEVS的界面的
主要是系统地学习一下悬线法这个看似十分简单，实际就是十分简单的算法
对于一些详细的东西参考dalao's blog，不喜勿喷
对于悬线法，其实是用来求二维平面内的最大（或者是其他）要求的子矩形的面积。其中的子矩形要满足以下两点性质：
子矩形的边要平行于大矩形的边，就是不能斜着
子矩形一定要满足某些性质，如本题中的全部为0
这时候我们可以用O(nm)的悬线法来solve这种问题
其实我们要做的就是DP出三个数组：
h[i][j]：表示第i行第j列向上包括自身最多一共有几个连续的0
l[i][j]：表示第i行第j列在保持以上的情况中，向左边（包括自身）最窄的宽度
r[i][j]：同上，只不过是向右的而已
所以，我们可以很轻易的得到：
ans=max(ans,(h[i][j]+l[i][j]-1)*h[i][j])
所以我们只需要处理处h,l,r数组即可
这里的转移很简单也很显然，自己看一下CODE中的转移即可
CODE
#include<cstdio>
using namespace std;
const int N=2005;
int h[N][N],l[N][N],r[N][N],a[N][N],n,ans;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline int min(int a,int b)
{
return a<b?a:b;
}
inline int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
register int i,j;
for (read(n),i=1;i<=n;++i)
{
for (j=1;j<=n;++j)
{
read(a[i][j]);
if (i!=1) h[i][j]=a[i-1][j]?!a[i][j]:h[i-1][j]+!a[i][j]; else h[i][j]=!a[i][j];
l[i][j]=a[i][j-1]?1:l[i][j-1]+1;
}
for (j=n;j>=1;--j)
r[i][j]=a[i][j+1]?1:r[i][j+1]+1;
}
for (i=1;i<=n;++i)
for (j=1;j<=n;++j)
if (!a[i][j])
{
if (i!=1&&!a[i-1][j]) l[i][j]=min(l[i][j],l[i-1][j]),r[i][j]=min(r[i][j],r[i-1][j]);
ans=max(ans,(r[i][j]+l[i][j]-1)*h[i][j]);
} else h[i][j]=l[i][j]=r[i][j]=0;
printf("%d",ans);
return 0;
}