C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int p,c,d;
int h[3010][3010];
int q[3010],hh[3010][3010],l[3010],r[3010];
int main()
{
cin>>p>>c>>d;
int i,j;
while(d--)
{
cin>>i>>j;
h[i][j]=1; //首先预处理将这些点处理一下
}
for(int i=1;i<=p;i++)
{
for(int j=1;j<=c;j++)
{
if(h[i][j]==0)hh[i][j]=hh[i-1][j]+1; //懂都懂,预处理将每个点的长度处理好,看不懂的输出一下就知道什么意思了。
}
}
int tt=0,res=0;
for(int i=1;i<=p;i++)
{
tt=0; q[0]=0;
hh[i][0]=hh[i][c+1]=-1;
for(int j=1;j<=c;j++)
{
while(hh[i][j]<=hh[i][q[tt]])tt--;
l[j]=q[tt];
q[++tt]=j;
}
tt=0,q[0]=c+1;
for(int j=c;j;j--) //记得j--,而不是加加,因为这是从后面遍历找右边的。
{
while(hh[i][j]<=hh[i][q[tt]])tt--;
r[j]=q[tt];
q[++tt]=j;
}
for(int j=1;j<=c;j++)
res=max(res, hh[i][j]*(r[j]-l[j]-1)); //不断的比较面积大小,取最大的。
}
cout<<res<<endl;
return 0;
}
其实题目就是模板题,相关题看其他单调栈问题,建议用数组模拟栈来深刻理解栈。
见其他例题 acwing.131 https://www.acwing.com/problem/content/133/
acwing.152 https://www.acwing.com/problem/content/154/
acwing.600 https://www.acwing.com/problem/content/602/
按照顺序来,慢慢理解,也算是不难吧 =。。=