2014
03-23

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)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮