hdu1506 Largest Rectangle in a Histogram--DP/栈
发布日期:2021-10-03 20:31:55 浏览次数:1 分类:技术文章

本文共 2268 字,大约阅读时间需要 7 分钟。

原题链接:

一:原题内容

Problem Description
A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:
Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.
 
Input
The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1 <= n <= 100000. Then follow n integers h1, ..., hn, where 0 <= hi <= 1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.
 
Output
For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.
 
Sample Input
7 2 1 4 5 1 3 34 1000 1000 1000 10000
 
Sample Output
84000

二:分析理解

利用stack来做,其实利用了压缩的思想,每个push进栈的值都是相较于前一个进栈的较小值。

三:AC代码

#include
#include
#include
#include
using namespace std;long long int heights[100005];//64位int main(){ int n; while (scanf("%d", &n) && n) { for (int i = 0; i < n; i++) scanf("%I64d", &heights[i]);//64位 stack
s; long long int ans = 0;//64位 for (int i = 0; i < n; i++) { if (s.empty() || heights[i]>heights[s.top()]) s.push(i); else { int cur = s.top(); s.pop(); long long int width = s.empty() ? i : i - s.top() - 1; ans = max(ans, width*heights[cur]); i--;//!!! } } while (!s.empty()) { int cur = s.top(); s.pop(); long long int width = s.empty() ? n : n - s.top() - 1; ans = max(ans, width*heights[cur]); } printf("%I64d\n", ans);//64位的输出,坑 } return 0;}

转载地址:https://blog.csdn.net/LaoJiu_/article/details/50954873 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:hdu1505 City Game--DP/栈
下一篇:hdu2845 Beans--DP

发表评论

最新留言

留言是一种美德,欢迎回访!
[***.207.175.100]2024年03月22日 08时40分28秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

php apc.dll下载,PHP之APC缓存详细介绍 apc模块安装 2019-04-21
html贝塞尔曲线在线,贝塞尔曲线的一些事情_html/css_WEB-ITnose 2019-04-21
java blockingqueue源码_Java并发队列BlockingQueue实现之ArrayBlockingQueue源码分析 2019-04-21
Java前台显示近20天的东西_第十次课:前台首页设计及显示商品信息 2019-04-21
java开发web网站的路由设计_理解Web路由(浅谈前后端路由与前后端渲染) 2019-04-21
excel如何把顺序倒过来_在excel中怎么使文字颠倒顺序反过来显示呢? 2019-04-21
java 62进制 转换_序列号生成的另一种玩法--62进制如何玩? 2019-04-21
php正则表达式获取图片路径,php 常用正则表达式实例(图片地址,与指定内容获取)... 2019-04-21
脚本语言php是什么意思,PHP脚本语言 2019-04-21
matlab数学规划模型,数学规划模型 2019-04-21
视频提取音频php,如何提取视频中的音频,从视频文件中提取出音频输出成MP3格式... 2019-04-21
diy.php添加验证码,织梦dedecms自定义表单中加入验证码 2019-04-21
在php脚本中 通过可以获取,在PHP中,可以使用Unix时间戳获取精确的脚本执行时间。... 2019-04-21
s2-045 php exp,S2-045-EXP.py --Struts2任意代码执行漏洞 (S2-045,CVE-2017-5638) 2019-04-21
linux sdk 窗口句柄,Venus: 针对Linux平台上,对常用的系统API进行面向对象的封装SDK。... 2019-04-21
c语言程序设计 科学出版社习题答案,C语言程序设计(科学出版社)第4章 课后习题参考答案.doc... 2019-04-21
c语言 无错 但只运行一半,求哈夫曼编码时程序运行到一半就终止了,编译无错... 2019-04-21
deepin linux 2014安装,2014.2版本的Deepin虚拟机安装浅谈(就是深度Linux) 2019-04-21
android 限速工具,Android下载器之限速篇 2019-04-21
html刷新ajax实现原理,AJAX的原理—如何做到异步和局部刷新 2019-04-21