南阳236----心急的C小加

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define inf 1<<30
 4 using namespace std;
 5 
 6 typedef struct
 7 {
 8     int l,w;
 9 } cus;
10 cus a[5005],d[5005];
11 int top;
12 
13 int cmp(cus x,cus y)
14 {
15     if(x.l == y.l)
16         return x.w < y.w;
17     return x.l < y.l;
18 }
19 
20 void solven(int x,int y)
21 {
22     int i;
23     for(i=0; i<=top; ++i)
24         if(d[i].l <= x && d[i].w <= y)
25         {
26             d[i].l = x;
27             d[i].w = y;
28             break;
29         }
30     if(i == top + 1)
31     {
32         d[++top].l = x;
33         d[top].w = y;
34     }
35 }
36 
37 int main()
38 {
39     int t,n,i;
40     scanf("%d",&t);
41     while(t--)
42     {
43         scanf("%d",&n);
44         for(i=0; i<n; ++i)
45         {
46             scanf("%d%d",&a[i].l,&a[i].w);
47         }
48         sort(a,a+n,cmp);
49         d[0].l = d[0].w = inf;
50         for(i=top=0; i<n; ++i)
51             solven(a[i].l,a[i].w);
52         printf("%d
",top);
53     }
54     return 0;
55 }