写一道CODEVS的题目

其实我还是很喜欢CODEVS的界面的

主要是系统地学习一下悬线法这个看似十分简单,实际就是十分简单的算法

对于一些详细的东西参考dalao's blog,不喜勿喷

对于悬线法,其实是用来求二维平面内的最大(或者是其他)要求的子矩形的面积。其中的子矩形要满足以下两点性质:

  1. 子矩形的边要平行于大矩形的边,就是不能斜着

  2. 子矩形一定要满足某些性质,如本题中的全部为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;
}
05-04 00:16