AcWing 152. 城市游戏 带注释
原题链接
中等
作者:
蓬蒿人
,
2021-05-21 23:33:05
,
所有人可见
,
阅读 432
#include <iostream>
using namespace std;
//题目要求我们找到由F组成的最大矩形 输出最大矩形面积*3
//作为直方图那题的拓展
//本题字符串n行m列 我们将1~n行的视作n个直方图(分别是1~1层,1~2层,...,1~n层)
//找到其中的最大的矩形
//最终 我们只要找n个直方图中的最大矩形就能得到答案
char g[2020][2020];
int n,m,f[2020][2020],q[10009];
int l[10009],r[10009];
int main (){
cin>>n>>m;
//直方图中我们知道每个柱子的高度 本题我们通过递推得到第i层直方图每根柱子的高度
//具体就是 当g[i][j]是'F'时 那么他的高度就是上层直方图柱子i的高度加一
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
cin>>g[i][j];
if (i==1) {
if (g[i][j]=='F') f[i][j]=1;
else f[i][j]=0;
}
else {
if (g[i][j]=='F') f[i][j]=f[i-1][j]+1;
//当g[i][j]是'F'时 那么他的高度就是上层直方图柱子i的高度加一
else f[i][j]=0;
}
}
}
long long res=0;
//然后就是直方图中最大矩形的求法了 只不过多了层循环
//因为我们将矩阵视作了n个直方图嘛 (分别是1~1层,1~2层,...,1~n层)
for (int i=1;i<=n;i++){
int tt=0;
f[i][0]=f[i][m+1]=-1;
q[0]=0;
for (int j=1;j<=m;j++){
while (f[i][j]<=f[i][q[tt]]) tt--;
l[j]=q[tt];
q[++tt]=j;
}
tt=0,q[0]=m+1;
for (int j=m;j;j--){
while (f[i][j]<=f[i][q[tt]]) tt--;
r[j]=q[tt];
q[++tt]=j;
}
for (int j=1;j<=m;j++) res=max(res,(long long)(r[j]-l[j]-1)*3*f[i][j]);
//res是long long (r[j]-l[j]-1)*3*f[i][j]也要强制类型转换成long long哦
}
cout<<res;
return 0;
}
牛皮
蓬蒿人牛皮!!!
蓬蒿人牛皮!!!