刷题总结——玉蟾宫(bzoj3039单调栈)
2024-08-22 20:48:45
题目:
Description
有一天,小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫,玉蟾宫宫主蓝兔盛情地款待了它们,并赐予它们一片土地。
这片土地被分成N*M个格子,每个格子里写着'R'或者'F',R代表这块土地被赐予了rainbow,F代表这块土地被赐予了freda。
现在freda要在这里卖萌。。。它要找一块矩形土地,要求这片土地都标着'F'并且面积最大。
但是rainbow和freda的OI水平都弱爆了,找不出这块土地,而蓝兔也想看freda卖萌(她显然是不会编程的……),所以它们决定,如果你找到的土地面积为S,它们每人给你S两银子。
Input
第一行两个整数N,M,表示矩形土地有N行M列。
接下来N行,每行M个用空格隔开的字符'F'或'R',描述了矩形土地。
Output
输出一个整数,表示你能得到多少银子,即(3*最大'F'矩形土地面积)的值。
Sample Input
5 6
R F F F F F
F F F F F F
R R R F F F
F F F F F F
F F F F F F
R F F F F F
F F F F F F
R R R F F F
F F F F F F
F F F F F F
Sample Output
45
HINT
对于50%的数据,1<=N,M<=200
对于100%的数据,1<=N,M<=1000
Source
题解:
首先枚举每一行,再枚举每一列算向上的最大高度····
至于宽度利用从左到右,从右到左两次单调栈枚举第一次小于该列高度的列的位置x,则x+1(x-1)要么是这一列,要么是第一个大于这一列的列(且x+1(x-1)到枚举的列的高度都大于等与枚举的这一列),从而算出矩形的最大值
代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int N=;
int map[N][N],stack[N],tail,n,m,height[N],Left[N],Right[N],ans=;
char c;
int main()
{
// freopen("a.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
c=getchar();
while(c!='F'&&c!='R') c=getchar();
if(c=='F') map[i][j]=;
}
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(map[i][j]) height[j]++;
else height[j]=;
}
tail=;
stack[]=;
for(int j=;j<=m;j++)
{
while(height[stack[tail]]>=height[j]&&tail) tail--;
Left[j]=stack[tail]+;
stack[++tail]=j;
}
tail=;
stack[]=m+;
for(int j=m;j>=;j--)
{
while(height[stack[tail]]>=height[j]&&tail) tail--;
Right[j]=stack[tail]-;
stack[++tail]=j;
}
for(int j=;j<=m;j++) ans=max(ans,height[j]*(Right[j]-Left[j]+));
}
cout<<ans*<<endl;
return ;
}
最新文章
- 购物车catslider简单的多商品分类滑动
- bootstrap-导航条
- Swift 中的函数(下)
- 利用WinHEX,重构狂牛加密视频1.0.0.1【只适合RIFF(AVI)】
- apache环境Zf2要装的intl验证
- zookeeper启动入口
- js的2种继承方式详解
- cocos2d-x学习笔记------动画人物跑起来吧!
- 查看mysql字符集及修改表结构--表字符集,字段字符集
- java连接sqL2008 数据库实例
- 控制流之if
- 【转载】从头编写 asp.net core 2.0 web api 基础框架 (1)
- python使用@property
- js事件流机制冒泡和捕获
- 【ACM】 1231 最大连续子序列
- 第三次Sprint
- [No0000167]CPU内部组成结构及指令执行过程
- sas 解析json
- 三种文本特征提取(TF-IDF/Word2Vec/CountVectorizer)及Spark MLlib调用实例(Scala/Java/python)
- linux中的ftp命令
热门文章
- uvm_test——测试用例的起点
- 生鲜o2o配送应用系统,包括Android源码+SSH带后台管理系统
- 【iview input 回车刷页面bug】input 就一个的时候 有form的时候 回车会刷页面,如果就一个input,可以不要form,或者form里面两个input 将一个input v-show false 就可以了
- CAD交互绘制云线批注(网页版)
- thinkphp网站后门-发现后门(Webshell)文件
- ES6新增";Promise";可避免回调地狱
- WPF显示尺寸与设备无关问题
- Greenplum/Deepgreen(集群/分布式)安装文档
- python安装mysql-connector出错
- 蓝牙学习 (8)配对raspberryPi和SensorTag CC2650