首页 > 其他 > 详细

HDU 1506 Largest Rectangle in a Histogram

时间:2014-03-18 12:07:53      阅读:433      评论:0      收藏:0      [点我收藏+]

题意大概是给你一幅柱状图,寻找里面最大的长方形的面积。

一类很典型的动态规划问题,我之前一直不会。QAQ

l[i] r[i]分别表示以i这个柱子为长方形的高,两边最多能够延伸到的位置。

如果l[i]的左边那一个的高度大于等于当前的高度,那么就可以延伸下去,一直更新到不能延伸下去为止。

即 while(h[l[i]-1]>=h[i]) l[i]=l[l[i]-1];

右边以同样的方式处理即可。

这个模型可以变换成很多情况,需要好好理解

 

bubuko.com,布布扣
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 100001;
int height[maxn],left_bound[maxn],right_bound[maxn];

#define max(a,b) (((a)>(b))?(a):(b))

int main() {
    int n;
    while(scanf("%d",&n),n) {
        for(int i = 1;i <= n;i++) {
            scanf("%d",&height[i]);
            left_bound[i] = right_bound[i] = i;
        }
        height[0] = height[n + 1] = -1;
        for(int i = 1;i <= n;i++) {
            while(height[left_bound[i] - 1] >= height[i]) {
                left_bound[i] = left_bound[left_bound[i] - 1];
            }
            int j = n - i + 1;
            while(height[right_bound[j] + 1] >= height[j]) {
                right_bound[j] = right_bound[right_bound[j] + 1];
            }
        }
        long long ans = 0;
        for(int i = 1;i <= n;i++) {
//            printf("%d %d\n",left_bound[i],right_bound[i]);
            ans = max(ans,height[i] * (right_bound[i] - left_bound[i] + 1LL));
        }
        printf("%lld\n",ans);
    }
    return 0;
}
bubuko.com,布布扣

HDU 1506 Largest Rectangle in a Histogram,布布扣,bubuko.com

HDU 1506 Largest Rectangle in a Histogram

原文:http://www.cnblogs.com/rolight/p/3606410.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!