HDU--3457--Rectangles--記憶化搜索

Rectangles
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 707    Accepted Submission(s): 284

Problem DescriptionA 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. 
InputThe 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. 
OutputFor each input test case, print a single integer indicating the length of the longest chain. 
Sample Input
3
1 5 2 8
3 -1 5 4
10 10 20 20
2
2 1 4 5
6 5 8 10
0
 
Sample Output
2
1
 

題意：給你N個矩形的左下角跟右上角坐標，然後找出這樣一組序列使得其中的每一項與它的後一項滿足一個條件，條件是前一項的右上角頂點的X，Y坐標都比後一項的左下角頂點的小，這樣的序列可能有多個，求出最長那個的長度（最後一項沒有後一項，你懂的，他就是最大的那個）

解析：用記憶化搜索來減少重復搜索的時間，做了很多記憶化搜索題目的人基本很快KO這個題

#include 
#include 
#include 
#include 
#define Max(a,b) a>b?a:b
using namespace std;
int n;
int dp[1111],map[1111][1111];
struct node
{
    int x1,x2,y1,y2;
}s[1111];
int dfs(int x)
{
    int i,j,k,l;
    if(dp[x])return dp[x];	//先前有數據了就不用再搜了
    for(i=0;i