算法

POJ2082总结

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 w1h1+w2h2+…+wnhn < 109.

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

我的代码

真不错,oj用英文体面真不错。

这个题目描述得很吓人,绕了一大圈子之后翻译翻译,就是给出连续的几个矩形求最大的子矩形的面积。我看网上很多人没有给出这道题的翻译,我来说一下我的推论:

集合B是在任意一个矩形内画出一道垂直线,然后以这道垂直线为宽、原点到垂线段的端点为长构成的矩形的集合。集合T是集合B的一个子集,满足于集合S的构造条件。

集合S的含义是最不好懂的,用一张图来说明:

qq screenshot 20200805144328 1

浅灰色的矩形是题目中给出的矩形;红色的矩形是B中满足条件的一个矩形(大小可变);蓝色矩形是长为W宽为H的矩形;绿色矩形是长为x0宽为y0的矩形;黑色矩形是蓝色矩形和绿色矩形联合起来占据的空间。那么可以知道黑色矩形其实就是集合T中的元素(向左平移至原点后可见),且集合S要求的最大值WH就是蓝色矩形的面积。

求子矩形的最大面积,可以遍历每一个矩形,作为子矩形的高,然后向左向右拓展,如果想要拓展的矩形高度高于该矩形则拓展成功,最后可以求出面积的最大值。这样做的效率是N^2,我不知道会不会超时。我从网友们那里学到了一个更厉害的算法:单调栈。

其实这个单调栈就有点动态规划的意思:想要用上第i+1个矩形,如果它不比第i个矩形矮,那么它是很随意的,因为它的高度不是决定最终子矩形高度的关键(可以直接入栈);如果不是那么第i+1个矩形前面第一个比它矮的矩形k,从k到i的矩形就算想要参与构建子矩形,其高度最高也只能用到第i+1个矩形的高度。

单调栈对第二种情况的处理很有讲究:首先就是要先对所有满足条件的矩形出栈,边出栈还要边结合起来看已经出栈的矩形能构成的面积的最大值;其次就是将所有出栈的矩形都削成和第i+1个矩形一样高的,再和这个矩形拼接成一个大矩形重新入栈。

#include<stdio.h>
#include<stack>

using namespace std;

int n,ans,width;
struct node{
	int w,h;
	node(){
		w=0;
		h=0;
	}
};
int main()
{
	while(scanf("%d",&n)==1&&n!=-1){
		node nodes[50010];
		stack<node> s;
		ans=-1;
		for (int i=0;i<n;i++){
			scanf("%d%d",&nodes[i].w,&nodes[i].h);
			width=0;
			if (s.empty()){
				s.push(nodes[i]);
			}else{
				if ((s.top()).h<nodes[i].h){
					s.push(nodes[i]);
				}else{
					while(!s.empty()){
						if ((s.top()).h>=nodes[i].h){
							width+=(s.top()).w;
							if ((width*(s.top()).h)>ans){
								ans=width*(s.top()).h;
							}
							s.pop();
						}else{
							break;
						}
					}
					nodes[i].w+=width;
					s.push(nodes[i]);
				}
			}
		}
		width=0;
		while(!s.empty()){
			width+=(s.top()).w;
			if ((width*(s.top()).h)>ans){
				ans=width*(s.top()).h;
			}
			s.pop();
		}
		printf("%d\n",ans);
	}
	return 0;
}