题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1160
其实也是最长递增子序列的问题。
按重量从小到大排序，找关于速度的最长递减子序列，并用pre数组记录前驱，最终存到vector里面输出路径。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<vector> 5 using namespace std; 6 const int maxn=1010; 7 int dp[maxn],pre[maxn]; 8 vector<int> v; 9 struct mouse 10 { 11 int w,v; 12 int id; 13 bool operator< (const mouse& a) 14 { 15 return w<a.w; 16 } 17 }p[maxn]; 18 19 int main() 20 { 21 int cnt=0; 22 int c=0; 23 while(scanf("%d%d",&p[cnt].w,&p[cnt].v)!=EOF) p[cnt++].id=++c; 24 { 25 v.clear(); 26 int anst=-1,ansi; 27 sort(p,p+cnt); 28 memset(pre,0,sizeof(pre)); 29 memset(dp,0,sizeof(dp)); 30 for(int i=0;i<cnt;i++) 31 { 32 dp[i]=1; 33 for(int j=0;j<i;j++) 34 if(p[j].v>p[i].v&&p[j].w<p[i].w&&dp[i]<dp[j]+1) //因为要求严格递增，判断条件要p[j].w<p[i].w 35 { 36 dp[i]=dp[j]+1; 37 pre[p[i].id]=p[j].id; 38 } 39 if(anst<=dp[i]) 40 { 41 anst=dp[i]; 42 ansi=p[i].id; 43 } 44 } 45 printf("%d ",anst); 46 for(int i=0;i<anst;ansi=pre[ansi],i++) 47 v.push_back(ansi); 48 for(int i=v.size()-1;i>=0;i--) 49 printf("%d ",v[i]); 50 } 51 }