本来实在做后缀数组的题目的,不巧,碰到了pku3415这题,需要用到单调栈来维护,但是之前又没有学习过单调栈这方面的知识,于是水了几题.......

题意:给你一些连续的小矩形,高宽不定,求最大的矩形面积........

思路:直接用单调栈,当有一个矩形的高小于等于栈顶元素的高时,出栈,并维护这个即将入栈的元素的向前延伸的宽度范围,维护出栈后的栈顶元素向后延伸的宽度范围.......

#include<iostream>
#include<stack>
#include<stdio.h>
using namespace std;
struct node
{
__int64 h,pre,next,w;
};
int main()
{
int n;
while(scanf("%d",&n)>0)
{
if(n==-1)
break;
stack<node>Q;
node tmp;
__int64 ans=0,sum=0,num;
scanf("%I64d%I64d",&tmp.w,&tmp.h);
tmp.pre=tmp.w;
tmp.next=tmp.w;
Q.push(tmp);
for(int i=1;i<n;i++)
{
scanf("%I64d%I64d",&tmp.w,&tmp.h);
tmp.pre=tmp.next=tmp.w;
while(!Q.empty()&&tmp.h<=Q.top().h)
{
node tmp1=Q.top();
Q.pop();
ans=tmp1.h*(tmp1.pre+tmp1.next-tmp1.w);
if(!Q.empty())
Q.top().next+=tmp1.next;
tmp.pre+=tmp1.pre;
if(ans>sum)
sum=ans;
}
Q.push(tmp);
}
while(!Q.empty())
{
node tmp1=Q.top();
Q.pop();
if(!Q.empty())
Q.top().next+=tmp1.next;
ans=tmp1.h*(tmp1.pre+tmp1.next-tmp1.w);
if(ans>sum)
sum=ans;
}
printf("%I64d\n",sum);
}
return 0;
}

最新文章

  1. 14 Iterator和for...of循环
  2. A strange lift
  3. 让PHP代码更危险----使用别的系统命令--如sql语句--exec(),system()方法甚至html的js语句
  4. GitHub入门:如何上传与下载工程?
  5. Networking - ARP 协议
  6. Spring的PropertyPlaceholderConfigurer应用
  7. Eclipse使用笔记
  8. 序列化TList of objects(摘自danieleteti的网站)
  9. HDU 2579/BFS/ Dating with girls(2)
  10. bzoj4816 [Sdoi2017]数字表格
  11. MySQL (二)-- 数据类型(列类型)、数值类型、 小数类型、 时间日期类型、 字符串类型 、 MySQL记录长度、列属性
  12. oracle的高级查询
  13. day12 十二、开放封闭、装饰器
  14. openstack placement
  15. XML Parsing Error: no element found Location: moz-nullprincipal:{23686e7a-652b-4348-92f4-7fb3575179ed} Line Number 1, Column 1:^
  16. SpringMVC注解集合
  17. 通过管理员命令进入D盘
  18. angular5 路由传参的几种方式
  19. Scanner的例子
  20. C++迭代器失效的几种情况总结

热门文章

  1. go语言基础之回调函数
  2. STM32F103 GU906B模块GPRS、短信收发、拨号等功能的实现
  3. WebSocket原理分析
  4. PyDev:warning: Debugger speedups using cython not foun
  5. .NET-MVC站点发布注意事项
  6. Cognos开发ContentManagerServiceStub不能转换为Stub
  7. [NPM] Avoid Duplicate Commands by Calling one NPM Script from Another
  8. STL - 移除(remove)和释放(erase)集合元素
  9. JSP生成静态html网页
  10. MS SQL得到指定日期的当月月末