Rectangles（第七届ACM省赛原题+最长上升子序列）

题目链接：

http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=1255

描述

Given N (4 <= N <= 100) rectangles and the lengths of their sides ( integers in the range 1..1,000), write a program that finds the maximum K for which there is a sequence of K of the given rectangles that can "nest", (i.e., some sequence P1, P2, ..., Pk, such that P1 can completely fit into P2, P2 can completely fit into P3, etc.).

A rectangle fits inside another rectangle if one of its sides is strictly smaller than the other rectangle's and the remaining side is no larger. If two rectangles are identical they are considered not to fit into each other. For example, a 2*1 rectangle fits in a 2*2 rectangle, but not in another 2*1 rectangle.

The list can be created from rectangles in any order and in either orientation.

输入

The first line of input gives a single integer, 1 ≤ T ≤10, the number of test cases. Then follow, for each test case：

* Line 1: a integer N , Given the number ofrectangles N<=100
* Lines 2..N+1: Each line contains two space-separated integers X Y, the sides of the respective rectangle. 1<= X , Y<=5000

输出

Output for each test case , a single line with a integer K , the length of the longest sequence of fitting rectangles.

样例输入

样例输出

 1 /*
 2 问题 输入n个矩形的两条边长，计算并输出满足嵌套条件的最大长度，嵌套条件是其中一个矩形的一条边小于两一个矩形的一条边，而另
 3 一条边小于等于另一个矩形的另一条边。
 4 
 5 解题思路
 6 比赛结束后，第一个重要的是读题读题读题。没有看到题目描述的最后一句话可以变换顺序及方向。导致没有排序，wa了7遍。
 7 其实思路很简单，读入的时候将n个矩形尽可能的放平，就是短边放前面，再将所有矩形排序，排序规则是先比较第一条边，小的在前，
 8 如果相等时比较第二条边，小的在前面（记得是小于，不确定的时候输出看一下）。然后就是最长上升子序列的模板了。 
 9 */
10 
11 #include<cstdio>
12 #include<algorithm>
13 using namespace std;
14 
15 struct REC{
16     int c,k;
17 }rec[110];
18 
19 int cmp(struct REC a,struct REC b){
20     if(a.c < b.c)
21         return 1;
22     else if(a.c == b.c)
23         return a.k < b.k;//先按照c排，在按照k排的关键，wa了两次 
24     return 0;
25 }
26 
27 int ok(struct REC a,struct REC b){
28     if((a.c > b.c && a.k >= b.k) || (a.k > b.k && a.c >= b.c))
29         return 1;
30     return 0;
31 }
32 
33 int main()
34 {
35     int T;
36     scanf("%d",&T);
37     int n,i,j,a[110]; 
38     while(T--){
39         scanf("%d",&n);
40         
41         int e1,e2;
42         for(i=1;i<=n;i++){
43             scanf("%d%d",&e1,&e2);
44             rec[i].c=e1<e2?e1:e2;//保证短边在前 
45             rec[i].k=e1<e2?e2:e1;
46         }
47         
48         sort(rec+1,rec+n+1,cmp); 
49         
50         /*for(i=1;i<=n;i++)
51             printf("%d %d
",rec[i].c,rec[i].k);*/ 
52         a[1]=1;
53         for(i=2;i<=n;i++){
54             int temp=0;
55             for(j=1;j<i;j++){
56                 if(ok(rec[i],rec[j])){
57                     if(temp < a[j])
58                         temp = a[j];
59                 }
60             }
61             a[i] = temp +1;
62         }
63         
64         int ans=-1;
65         for(i=1;i<=n;i++){
66             if(a[i] > ans)
67                 ans = a[i];
68         }
69         printf("%d
",ans);
70     }
71     return 0;
72 }