hdoj 1160

一道dp的题。。。。 
1 //求最长下降子序列
 2 #include <iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 struct node{
 6     int w,s,order;//order为存入时的顺序
 7 }q[1002];//存储信息
 8 int f[1002];
 9 int p[1002];//记录他的前一个信息
10 bool cmp(node a,node b){
11     if(a.w==b.w)
12         return a.s>b.s;
13     return a.w<b.w;//将信息按重量的大小排序
14 }
15 void prit(int a){
16     if(p[a]==a)//最大值其位置肯定是p【a】=a
17         cout<<q[a].order<<endl;
18     else{
19         prit(p[a]);
20         cout<<q[a].order<<endl;
21     }
22 }
23 int main()
24 {
25     int cnt=1;
26    while(cin>>q[cnt].w>>q[cnt].s){
27         q[cnt].order=cnt;//记录他原来的位置
28         cnt++;
29     }
30     sort(q,q+cnt,cmp);//顺序已变
31     f[1]=1;
32     p[1]=1;
33     for(int i=2;i<cnt;i++){
34             int max = 0;
35             int idx = i;
36         for(int j=1;j<i;j++){
37             if(q[j].w<q[i].w&&q[j].s>q[i].s&&f[j]>max){
38                 max = f[j];
39                 idx = j;
40             }
41         }
42         f[i] = max+1;
43         p[i]= idx;
44     }
45     int max = 0;
46     int idx = 0;
47     for(int i=1;i<cnt;i++){//寻找最大的值
48         if(f[i]>max){
49             max= f[i];
50             idx = i;
51         }
52     }
53     cout<<max<<endl;
54     prit(idx);//输出其序号
55     return 0;
56 }