hdu 1160(最长递增子序列+输出）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1160

思路：就是排序后求最长递增子序列，只不过多了一个判断（s下降）以及最后输出下标，我们可以用一个pre[]数组来记录路径，最后递归输出就行了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define MAXN 1010
 7 struct Mice{
 8     int w,s,id;
 9 }mice[MAXN];
10 int n;
11 int dp[MAXN];
12 int pre[MAXN];
13 
14 int cmp(const Mice &p,const Mice &q){
15     if(p.w!=q.w)
16         return p.w<q.w;
17     return p.s>q.s;
18 }
19 
20 void Print(int x){
21     if(pre[x]==-1){
22         printf("%d\n",mice[x].id);
23         return ;
24     }
25     Print(pre[x]);
26     printf("%d\n",mice[x].id);
27 }
28 
29 
30 int main(){
31     int ans,ed,i=1;
32     while(scanf("%d%d",&mice[i].w,&mice[i].s)==2)mice[i].id=i,i++;
33     n=i-1;
34     sort(mice+1,mice+n+1,cmp);
35     memset(dp,0,sizeof(dp));
36     memset(pre,-1,sizeof(pre));
37     for(int i=1;i<=n;i++){
38         ans=0;
39         for(int j=1;j<i;j++){
40             if(mice[i].w>mice[j].w&&mice[i].s<mice[j].s&&ans<dp[j]){
41                 ans=dp[j];
42                 pre[i]=j;
43             }
44         }
45         dp[i]=ans+1;
46     }
47     ans=0,ed=-1;
48     for(int i=1;i<=n;i++){
49         if(dp[i]>ans){ans=dp[i],ed=i;}
50     }
51     printf("%d\n",ans);
52     Print(ed);
53     return 0;
54 }

View Code