解题思路
单调队列
+ 考虑暴力:枚举上下边界+枚举左右边界+枚举框内元素 => $O(n^6)$
+ 优化:枚举下边界 => 转化为 AcWing 131. 直方图中最大的矩形
单调栈模板
常见模型:找出每个数左/右边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (tt && check(stk[tt], i)) tt -- ;
stk[ ++ tt] = i;
}
AC代码
- 单调栈中存的是下标
- 设置两个哨兵,避免边界判断
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=3010;
int g[N][N];
int h[N][N];
int n,m,p;
int stk[N],tt;
int l[N],r[N];
int work(int h[])
{
h[0]=h[m+1]=-1;
tt=0;
stk[++tt]=0;
for(int i=1;i<=m;i++)
{
while(h[stk[tt]]>=h[i]) tt--;
l[i]=stk[tt];
stk[++tt]=i;
}
tt=0;
stk[++tt]=m+1;
for(int i=m;i>0;i--)
{
while(h[stk[tt]]>=h[i]) tt--;
r[i]=stk[tt];
stk[++tt]=i;
}
int res=-1;
for(int i=1;i<=m;i++)
res=max(res,(r[i]-l[i]-1)*h[i]);
return res;
}
int main()
{
cin>>n>>m>>p;
for(int i=0;i<p;i++)
{
int x,y;
cin>>x>>y;
g[x][y]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!g[i][j])
h[i][j]=h[i-1][j]+1;
int res=-1;
for(int i=1;i<=n;i++)
res=max(res,work(h[i]));
cout<<res;
return 0;
}