题目链接:传送门
题解:
方法二见【WC2002】奶牛浴场
悬线法求极大子矩阵,复杂度 <nobr> O(n2) </nobr>
讲解戳这里
//by sdfzchy
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int N=2005;
using namespace std;
typedef long long LL;
int n;
int h[N],l[N],r[N],ans;
bool a[N][N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
memset(r,0x3f,sizeof(r));
for(int i=1;i<=n;i++)
{
int L=1,R=n;
for(int j=1;j<=n;j++)
if(a[i][j])
{
L=j+1;
h[j]=l[j]=0;
}
else
{
h[j]++;
l[j]=max(l[j],L);
}
for(int j=n;j>=1;j--)
if(a[i][j])
{
R=j-1;
r[j]=n;
}
else
{
r[j]=min(r[j],R);
ans=max(ans,(r[j]-l[j]+1)*h[j]);
}
}
printf("%d\n",ans);
return 0;
}