首页 > ACM题库 > HDU-杭电 > HDU 3457-Rectangles[解题报告]HOJ
2014
03-23

HDU 3457-Rectangles[解题报告]HOJ

Rectangles

问题描述 :

A rectangle in the Cartesian plane is speci ed by a pair of coordinates (x1 , y1) and (x2 , y2) indicating its lower-left and upper-right corners, respectively (where x1 ≤ x2 and y1 ≤ y2). Given a pair of rectangles,A = ((xA1 , yA1 ), (xA2 ,yA2 )) and B = ((xB1 , yB1 ), (xB2 , yB2 )), we write A ≤ B (i.e., A "precedes" B), if xA2 < xB1 and yA2 < yB1 :In this problem, you are given a collection of rectangles located in the two-dimension Euclidean plane. Find the length L of the longest sequence of rectangles (A1,A2,…,AL) from this collection such that A1 ≤ A2 ≤ … ≤ AL.

输入:

The input fi le will contain multiple test cases. Each test case will begin with a line containing a single integer n (where 1 ≤ n ≤ 1000), indicating the number of input rectangles. The next n lines each contain four integers xi1 ,yi1 ,xi2 ,yi2 (where -1000000 ≤ xi1 ≤ xi2 ≤ 1000000, -1000000 ≤ yi1 ≤ yi2 ≤ 1000000, and 1 ≤ i ≤ n), indicating the lower left and upper right corners of a rectangle. The end-of-file is denoted by asingle line containing the integer 0.

输出:

The input fi le will contain multiple test cases. Each test case will begin with a line containing a single integer n (where 1 ≤ n ≤ 1000), indicating the number of input rectangles. The next n lines each contain four integers xi1 ,yi1 ,xi2 ,yi2 (where -1000000 ≤ xi1 ≤ xi2 ≤ 1000000, -1000000 ≤ yi1 ≤ yi2 ≤ 1000000, and 1 ≤ i ≤ n), indicating the lower left and upper right corners of a rectangle. The end-of-file is denoted by asingle line containing the integer 0.

样例输入:

3
1 5 2 8
3 -1 5 4
10 10 20 20
2
2 1 4 5
6 5 8 10
0

样例输出:

2
1

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
struct po{
	int x1,y1,x2,y2;
}a[1001];
bool cmp(po x,po y){
	if(x.x1==y.x1) return x.y1<y.y1;
	return x.x1<y.x1;
}
int dp[1002];
int main(){
	int n,xs,x,y,i,j;
	while(~scanf("%d",&n),n){
		memset(dp,0,sizeof(dp));
		for(i=0;i<n;i++){
			scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
		}
		sort(a,a+n,cmp);
		for(i=0;i<n;i++) dp[i]=1;
		for(i=1;i<n;i++){
			for(j=0;j<n;j++){
				if(a[i].x1>a[j].x2&&a[i].y1>a[j].y2){
					dp[i]=max(dp[i],dp[j]+1);
				}
			}
		}
		int mi=0;
		for(i=0;i<n;i++) mi=max(mi,dp[i]); 
		printf("%d\n",mi);
	}
	return 0;
}
//2 3 4

  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮