本文主要是介绍HDU1506 ( Largest Rectangle in a Histogram ) [dp]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最近情绪太不稳定了，可能是因为在找实习这个过程碰壁了吧，第一次面试就跪了，可能是我面的是一个新公司，制度不完善，我感觉整个面试过程完全不沾编程，我面试的还是软件开发～后来我同学面试的时候，说是有一道数学题了，最后都已经签了，orz...其他同学都陆续签了，有签了知乎，有签了猎豹的，有签了阿里的，我还在想着打比赛，作为一个快大四的人，我还想着打比赛，甚至我连队友都快没了～但是我还想坚持！到现在，我基本没课了，每天都只能是刷刷题，写写python，搞搞shell,我都不知道我在干嘛～！有没有大神给我来份实习啊！！！（还是要自己去找的..）其实，对比那些签了约的同学，一开始我就很不服输，我觉得明明我应该相比他们“厉害”啊，后来，我发现，我还是太弱了，火候没够，再坚持一把吧！
因为随时都可能组不成队伍，所以我每天刷题的时间不超过三个小时，更多时候只是一个小时，就是早起来刷一题。最近一直在做dp.但是今天做一题我做过的题目都弄了很久，烦死，思想不集中！
题目的意思就是，在直方图中找一个面积最大的矩形。思想就是dp咯，就是对于每一个小矩形向外扩展，直到扩展到比它矮，这样这个小矩形所组成的面积就是最大了，但是在扩展这个过程注意迭代，不然就会跪在TLE了，n^2必超的啊。
/***********************************************************> OS : Linux 3.2.0-60-generic #91-Ubuntu> Author : yaolong> Mail : dengyaolong@yeah.net > Time : 2014年06月01日 星期日 07:14:54**********************************************************/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
int h[123456];
int lt[123456],rt[123456];
int main(){int n;while(scanf("%d",&n)&&n){for(int i=1;i<=n;i++){scanf("%d",&h[i]);}long long res=0LL;rt[n]=n;lt[1]=1;for(int i=n-1;i>=1;i--){/*if(h[i]<=h[i+1]){rt[i]=rt[i+1];}else{rt[i]=i;}*/int t=i;while(t<n&&h[i]<=h[t+1]) t=rt[t+1];rt[i]=t;}for(int i=2;i<=n;i++){/*if(h[i]<=h[i-1]){lt[i]=lt[i-1];}else{lt[i]=i;}*/int t=i;while(t>1&&h[i]<=h[t-1]) t=lt[t-1];lt[i]=t;} for(int i=1;i<=n;i++){res=max(res,(long long)h[i]*(rt[i]-lt[i]+1));}printf("%I64d\n",res);}return 0;
}
这篇关于HDU1506 ( Largest Rectangle in a Histogram ) [dp]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
