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