矩形嵌套

 1 /*
 2 不是贪心，若是先按长排序在按宽，若是长很大宽很小 ,则若是后边款稍微大一些就不行了
 3 */
 4 #include <stdio.h>
 5 #include <iostream>
 6 #include <cstring>
 7 #include <algorithm>
 8 using namespace std;
 9
10 const int N = 1005;
11 typedef struct Node
12 {
13     int a;
14     int b;
15 }Node;
16 Node q[N];
17 int n;
18 int d[N];
19
20 bool cmp(const Node &a, const Node &b)
21 {
22     if (a.a == b.a)
23         return a.b < b.b;
24     return a.a < b.a;
25 }
26
27 bool judge(int i, int j)
28 {
29     bool flag = q[i].a>q[j].a && q[i].b>q[j].b;
30     if (flag)
31     {
32         return true;
33     }
34     return false;
35 }
36
37 int main()
38 {
39     int T;
40     int a, b;
41     int i,j,k;
42     cin>>T;
43     while (T--)
44     {
45         cin>>n;
46         for (i=1; i<=n; i++)
47         {
48             cin>>a>>b;
49             if (a>b)
50             {
51                 swap(a, b);
52
53             }
54             q[i].a = a;
55             q[i].b = b;
56         }
57
58         sort(q+1, q+n+1, cmp);
59         int ans = 1;
60         for (i=1; i<N; i++)
61         {
62             d[i] = 1;
63         }
64
65         for (i=2; i<=n; i++)//递推
66         {
67             for (j=i-1; j>0; j--)
68             {
69                 if (judge(i, j))
70                 {
71                     int temp = d[j] + 1;//数组d必须要初始化
72                     if(d[i]>temp)
73                        d[i] = temp;
74                 }
75             }
76             if(ans>d[i])
77                  ans = d[i];
78
79         }
80         cout<<ans<<endl;
81     }
82     system("pause");
83     return 0;
84 }