HDU1160:FatMouse's Speed(最长上升子序列，不错的题）

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

学的东西还是不深入啊，明明会最长上升子序列，可是还是没有A出这题，反而做的一点思路没有，题意就不多说了，真是怀疑了为什么做这题的时候竟然想用nlog(n)的那个算法，

根本不可能有解啊，真想抽自己一下，最后无奈看了题解，发现他们写的非常棒，记录路径仅用一个数组就可以实现，可惜我没有想到啊，还是做题不深入啊。

首先需要排一下序。

代码如下：

#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <queue> #include <math.h> #define inf 0x3f3f3f3f typedef long long ll; using namespace std; int n,da[1010][1010],dp[1010]; struct node {int id,w,s; } q[1010]; int cmp(const void *a,const void *b) {struct node *aa=(struct node *)a;struct node *bb=(struct node *)b;if(aa->w!=bb->w)return aa->w-bb->w;else return bb->s-aa->s; } int main() {int tt,maxx=1;;tt=0;while(scanf("%d%d",&q[tt].w,&q[tt].s)!=EOF){if(q[tt].w==0) break;q[tt].id=tt+1;tt++;}qsort(q,tt,sizeof(q[0]),cmp);for(int i=0;i<tt;i++){da[i][1]=q[i].id;//da[i][j]数组用来保存以i开头的最长序列,为j。dp[i]=1;//最短也包括它本身，为1,dp的初始化特别重要 }int x=0;for(int i=1;i<tt;i++){for(int j=0;j<i;j++){if(q[i].w>q[j].w&&q[i].s<q[j].s&&dp[j]+1>dp[i]){dp[i]=max(dp[i],dp[j]+1);for(int k=1;k<dp[i];k++){da[i][k]=da[j][k];}da[i][dp[i]]=q[i].id;//不断更改路径，大神们写的真好}}if(dp[i]>maxx){maxx=dp[i];x=i;}}printf("%d\n",maxx);for(int i=1;i<=maxx;i++){printf("%d\n",da[x][i]);}return 0; }

 

总结

以上是生活随笔为你收集整理的HDU1160:FatMouse's Speed(最长上升子序列，不错的题）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。