HDU 1506 Largest Rectangle in a Histogram

ゞ浴缸里的玫瑰 2022-04-16 04:21 89阅读 0赞

## 原题目链接[HDU1506][] ##

--------------------

## 分类 ##

HDU 动态规划

--------------------

## 题意 ##

给你一个直方图，告诉你各个条形矩形的高度，求基线对齐构成的矩形中面积  
最大的矩形的面积对于每一个矩形。

## 样例输入输出 ##

Sample Input

7 2 1 4 5 1 3 3
    4 1000 1000 1000 1000
    0

Sample Output

8
    4000

--------------------

## 想法 ##

对于每一个a\[i\],用dp找出a\[i\]左边和右边连续大于自己的数的长度  
l\[i\]表示比a\[i\]大的数连续的最左边的位置  
r\[i\]表示比a\[i\]大的数连续的最右边的位置

--------------------

## 代码 ##

106ms

#include<stdio.h>
    #include<string.h>
     
    int l[100010],r[100010];
    __int64 h[100010];
    int main()
    { 
        int N;
        while(~scanf("%d",&N) && N!=0)
        { 
            memset(h,0,sizeof(h));
            for(int i = 1; i <= N; i++)
            { 
                scanf("%I64d",&h[i]);
                l[i] = r[i] = i;
            }
     
            l[0] = 1;
            r[N+1] = N;
            h[0] = -1;
            h[N+1] = -1;
            //这上边不加就会超时，不加的话下边就可能一直while，跳不出循环
            for(int i = 1; i <= N; i++)
            { 
                while(h[l[i]-1] >= h[i])//找位置i的左边界
                    l[i] = l[l[i]-1];
            }
            for(int i = N; i >= 1; i--)
            { 
                while(h[r[i]+1] >= h[i])//找位置i的右边界
                    r[i] = r[r[i]+1];
            }
            __int64 MaxArea = -0xffffff0;
            for(int i = 1; i <= N; i++)
            { 
                if(h[i]*(r[i]-l[i]+1) > MaxArea)
                    MaxArea = h[i]*(r[i]-l[i]+1);
            }
            printf("%I64d\n",MaxArea);
        }
        return 0;
    }

[HDU1506]: http://acm.hdu.edu.cn/showproblem.php?pid=1506