Posted on 2008-03-25 21:50
superman 閱讀(1080)
評論(1) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1108 C++ 00:00.02 876K */
2 #include <stdlib.h>
3 #include <iostream>
4
5 using namespace std;
6
7 struct Mice { int w, s, num; } mice[1001];
8
9 void output(int path[], int pos)
10 {
11 if(pos == 0)
12 return;
13 output(path, path[pos]);
14 cout << mice[pos].num << endl;
15 }
16
17 int cmp(const void * a, const void * b)
18 {
19 Mice* c = (Mice*) a;
20 Mice* d = (Mice*) b;
21 if(c -> w == d -> w)
22 return d -> s - c -> s;
23 return c -> w - d -> w;
24 }
25
26 int main()
27 {
28 int n = 1;
29 while(cin >> mice[n].w >> mice[n].s)
30 {
31 mice[n].num = n;
32 n++;
33 }
34 qsort(mice + 1, n, sizeof(Mice), cmp);
35
36 int opt[1001] = {0, 1}, path[1001] = {0};
37
38 for(int i = 2; i <= n; i++)
39 {
40 for(int j = 1; j < i; j++)
41 if(mice[i].w > mice[j].w && mice[i].s < mice[j].s)
42 if(opt[i] < opt[j])
43 {
44 opt[i] = opt[j];
45 path[i] = j;
46 }
47 opt[i]++;
48 }
49
50 int max = 0, pos;
51 for(int i = 1; i <= n; i++)
52 if(opt[i] > max)
53 {
54 max = opt[i];
55 pos = i;
56 }
57 cout << max << endl;
58 output(path, pos);
59
60 return 0;
61 }
62