首页 > ACM题库 > HDU-杭电 > HDU 1506 Largest Rectangle in a Histogram-计算几何-[解题报告]
2013
12-12

HDU 1506 Largest Rectangle in a Histogram-计算几何-[解题报告]

Largest Rectangle in a Histogram

问题描述 :

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.

输入:

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1 <= n <= 100000. Then follow n integers h1, …, hn, where 0 <= hi <= 1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

输出:

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

样例输入:

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

一道写了很久的题,以前看过,都没什么感觉,今天终于把它搞懂了。很多人都说是DP,但我没感觉出来,好像就是YY题了。

题目中叫求一个最大的区域,则第i个矩形对应的面积是ave[i] = (r[i] – l[i] + 1) * a[i];l[i]表示以它这个高度所能到达的最左边的位置(最左一个高度不小于它的高度的位置),而r[i]表示能到达的最右边的位置(最右一个高度不小于它的高度的位置)。

那么这个题目就转到怎么求r[]和l[]上了。如果每次依次向左向右找,肯定会超时的。这时就会用到迭代了,比如说求a[i]的l[i],如果a[i]大于a[i-1]那么l[i] = i,这个不难理解,不解释;如果a[i]小于a[i-1],那么l[i]肯定小于l[i-1],找l[i]就可以直接跳到l[i-1]的位置上,在往左去找了。

#include <iostream>
using namespace std;

__int64 a[100005];
int r[100005];
int l[100005];

int main()
{
	int n,i,k;
	while(scanf("%d",&n)!=EOF && n!=0)
	{
		scanf("%d",&a[1]);
		l[0] = 0;
		l[1] = 1;
		for(i=2;i<=n;i++)
		{
			scanf("%d",&a[i]);
			if(a[i] > a[i-1])
				l[i] = i;
			else
			{
				k = i;
				while(k--)
				{
					if(a[k] < a[i])
					{
						l[i] = k+1;
						break;
					}
					else
					{
						k = l[k];
					}
				}
			}
		}
		r[n] = n;
		for(i=n-1;i>=1;i--)
		{
			if(a[i] > a[i+1])
				r[i] = i;
			else
			{
				k = i;
				while((++k) != n+1)
				{
					if(a[k] < a[i])
					{
						r[i] = k-1;
						break;
					}
					else
					{
						k = r[k];
					}
				}
				if(k == n+1)
					r[i] = n;
			}
		}

		__int64 max = 0;
		for(i=1;i<=n;i++)
		{
			__int64 ave = (r[i] - l[i] + 1) * a[i];
			if(ave > max)
				max = ave;
		}
		printf("%I64d/n",max);
	}
	return 0;
}

解题报告转自:http://blog.csdn.net/yrhsilence/article/details/5801692


  1. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  2. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!

  3. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

  4. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  5. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }