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