【题目链接】 http://poj.org/problem?id=2082

【题目大意】

  给出一些长方形下段对其后横向排列得到的图形,现在给你他们的高度,
  求里面包含的最大长方形的面积

【题解】

  我们枚举每个位置的最大高度全部被保留时得到的最优解,那么答案一定被包含在其中,
  那么题目转化为求出每个高度左右两边最近的比其低的位置,可以用单调栈完成。

【代码】

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N=100000;
int n,h[MAX_N],L[MAX_N],R[MAX_N],st[MAX_N],w[MAX_N],s[MAX_N];
void solve(){
int top=0;
for(int i=0;i<n;i++){
while(top>0&&h[st[top-1]]>=h[i])top--;
L[i]=top==0?0:(st[top-1]+1);
st[top++]=i;
}top=0;
for(int i=n-1;i>=0;i--){
while(top>0&&h[st[top-1]]>=h[i])top--;
R[i]=top==0?0:st[top-1];
st[top++]=i;
}
long long res=0;
for(int i=0;i<n;i++){
res=max(res,(long long)h[i]*(s[R[i]]-s[L[i]]));
}printf("%lld\n",res);
}
int main(){
while(scanf("%d",&n),n!=-1){
for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&h[i]),s[i+1]=s[i]+w[i];
h[n+1]=0;n+=2;
solve();
}return 0;
}

最新文章

  1. 定义返回Block的函数
  2. 5.django笔记之form保存表单信息,动态select
  3. C++类型转化
  4. 转: Android开发中的MVP架构详解(附加链接比较不错)
  5. maven详解之结构
  6. poi导出Excel直接在浏览器下载
  7. Java运行原理及内存分析
  8. servlet之ServletRequest与ServletResponse (三)
  9. emacs 绑定快捷键 c/c++
  10. 利用Oracle分析函数row_number和sys_connect_by_path实现多行数据合并为一行
  11. 1-2-编译U-boot
  12. PB函数大全【转自 http://blog.csdn.net/xiaoxian8023 】
  13. java实验报告二
  14. DLL文件实现窗体的模板模式
  15. 用c写了个后台扫描
  16. 【spring教程之中的一个】创建一个最简单的spring样例
  17. 20145311 《Java程序设计》第七周学习总结
  18. Linux 用户和组的 添加/删除
  19. fidder工具学习抓取Firefox包
  20. node.js Web应用框架Express入门指南

热门文章

  1. watch用法小记
  2. WCF分布式开发步步为赢(13):WCF服务离线操作与消息队列MSMQ
  3. GROUP_CONCAT(expr)
  4. WebView使用--文章集锦
  5. 如何实现用户id生成一个唯一邀请码
  6. 【洛谷 P3805】 【模板】manacher算法
  7. [bzoj2124]等差子序列——线段树+字符串哈希
  8. Swift, Playgrounds, and XCPlayground
  9. camera摄像原理之二:色彩空间【转】
  10. JQ子页面对父页面的元素进行操作