Largest Rectangle in a Histogram

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 12865    Accepted Submission(s): 3621

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.

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

8
4000

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1506

题目大意：一排木板并排放，宽都是1，高是输入值，求所包含面积中的最大子矩形的面积

题目分析：由于本题的n比较大1e5，因此O(n^2)直接枚举的做法肯定T，我们考虑对其进行优化，对于每个木板，如果其左边或者右边的值大于等于它的值，则可以将它的左边界或右边界向左或向右延伸，这个很好理解，因为它的高度最小，假设为h1，则以其为中心扩展出的最大的矩形面积为h1*(区间长度)

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
int const MAX = 100005;
int h[MAX], l[MAX], r[MAX];

int main()
{
    int n;
    while(scanf("%d", &n) != EOF && n)
    {
        h[0] = h[n + 1] = -1; //这里初始化的值必须小于0，否则因为高度可能为0，左边界数组下标可能变为－1
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &h[i]);
            l[i] = r[i] = i;
        }
        for(int i = 1; i <= n; i++)
        {
            while(h[i] <= h[l[i] - 1])
            {
                l[i] = l[l[i] - 1];
                if(h[l[i]] == 0)
                    break;
            }
        }
        for(int i = n; i >= 1; i--)
        {
            while(h[i] <= h[r[i] + 1])
            {
                r[i] = r[r[i] + 1];
                if(h[r[i]] == 0)
                    break;
            }
        }
        ll ans = 0;
        for(int i = 1; i <= n; i++)
            ans = max(ans, (ll)h[i] * (ll)(r[i] - l[i] + 1));
        printf("%I64d\n", ans);
    }
}

dp的路好难走，越难越要走

HDU 1506 Largest Rectangle in a Histogram (线性dp)

原文：http://blog.csdn.net/tc_to_top/article/details/44651839