HDU 1506 Largest Rectangle in a Histogram-蒲公英云

HDU 1506 Largest Rectangle in a Histogram

原题目链接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;
}