【POJ】2082 - Terrible Sets（单调栈）

点击打开题目

Terrible Sets

Description

Let N be the set of all natural numbers {0 , 1 , 2 , . . . }, and R be the set of all real numbers. wi, hi for i = 1 . . . n are some elements in N, and w0 = 0. Define set B = {< x, y > | x, y ∈ R and there exists an index i > 0 such that 0 <= y <= hi ,∑ 0<=j<=i-1wj <= x <= ∑ 0<=j<=iwj} Again, define set S = {A| A = WH for some W , H ∈ R + and there exists x0, y0 in N such that the set T = { < x , y > | x, y ∈ R and x0 <= x <= x0 +W and y0 <= y <= y0 + H} is contained in set B}. Your mission now. What is Max(S)? Wow, it looks like a terrible problem. Problems that appear to be terrible are sometimes actually easy. But for this one, believe me, it's difficult.

Input

The input consists of several test cases. For each case, n is given in a single line, and then followed by n lines, each containing wi and hi separated by a single space. The last line of the input is an single integer -1, indicating the end of input. You may assume that 1 <= n <= 50000 and w 1h 1+w 2h 2+...+w nh n < 10 9.

Output

Simply output Max(S) in a single line for each case.

Sample Input

3
1 2
3 4
1 2
3
3 4
1 2
3 4
-1

Sample Output

12
14

Source

Shanghai 2004 Preliminary

题目看的有点眼花。

这道题就是给出一堆连续矩形的长和宽，其包括的某一个矩形面积最大，求这个最大面积。

这道题用一个叫单调栈的知识点来做，所谓单调栈，肯定栈内的元素要单调，我这里的栈是递增的（可以等于），如果输入了比前面小的矩形，就把大矩形弹出，每次弹出都更新下ans值，并且记录总的宽度，最后把这些矩形的宽度和输入矩形的宽度合并组成一个新的矩形，这样这个栈就是一个单调栈了。最后一次输入完成后，再一个个的弹出更新ans。

代码如下：

#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
struct node
{
	int w,h;
}pr,ne;
int main()
{
	int n;
	int ans;
	int sumw;
	while (~scanf ("%d",&n) && n != -1)
	{
		stack<node> s;
		ans = 0;
		for (int i = 1 ; i <= n ; i++)
		{
			scanf ("%d %d",&pr.w,&pr.h);
			ans = max (ans , pr.w * pr.h);
			if (s.empty())
				s.push(pr);
			else		//进行单调栈的入栈 
			{
				sumw = 0;
				while (!s.empty())		//遇到大于等于它的都弹出并更新ans 
				{
					ne = s.top();
					if (ne.h < pr.h)
						break;
					sumw += ne.w;
					ans = max (ans , ne.h * sumw);
					s.pop();
				}
				ne.w = sumw + pr.w;
				ne.h = pr.h;
				s.push(ne);
			}
		}
		sumw = 0;
		while (!s.empty())
		{
			pr = s.top();
			sumw += pr.w;
			ans = max (ans , sumw * pr.h);
			s.pop();
		}
		printf ("%d\n",ans);
	}
	return 0;
}