Posted on 2008-03-26 23:38
superman 閱讀(517)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1025 C++ 00:00.16 924K */
2 #include <string.h>
3 #include <iostream>
4
5 using namespace std;
6
7 struct Stick { int l, w; } stick[5000];
8
9 int cmp(const void * a, const void * b)
10 {
11 Stick * c = (Stick*) a;
12 Stick * d = (Stick*) b;
13 if(c -> l == d -> l)
14 return c -> w - d -> w;
15 return c -> l - d -> l;
16 }
17
18 int main()
19 {
20 int n;
21 cin >> n;
22 while(cin >> n)
23 {
24 for(int i = 0; i < n; i++)
25 cin >> stick[i].l >> stick[i].w;
26
27 qsort(stick, n, sizeof(Stick), cmp);
28
29 bool x[5000] = {0};
30 int count = 0, m = n;
31 while(m)
32 {
33 int k, curL, curW;
34 for(k = 0; k < n; k++)
35 if(x[k] == 0)
36 break;
37 curL = stick[k].l;
38 curW = stick[k].w;
39 for(int i = k; i < n; i++)
40 if(x[i] == 0)
41 if(stick[i].l >= curL && stick[i].w >= curW)
42 {
43 m--;
44 x[i] = 1;
45 curL = stick[i].l;
46 curW = stick[i].w;
47 }
48 count++;
49 }
50
51 cout << count << endl;
52 }
53
54 return 0;
55 }
56