本文主要是介绍hdu 1160 FatMouse's Speed(最长上升子序列 +记录路径)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=1160
题意：有若干只老鼠，给出每只老鼠的大小和速度。输出尽量多的老鼠的下标m1,m2,m3......满足下标对应的老鼠大小严格递增而老鼠速度严格递减。
思路：先对老鼠的速度从大到小排序，在对老鼠的大小求最长上升子序列。在这过程中，用pre[ ]记录路径。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;struct node
{int size;int weight;int id;bool operator < (const struct node tmp)const{if(weight == tmp.weight)return size < tmp.size;return weight > tmp.weight;}
}mice[1010];int cnt,pre[1010],dp[1010];
int maxans,maxid;void solve()
{memset(pre,-1,sizeof(pre));for(int i = 1; i <= cnt; i++){dp[i] = 1;for(int j = 1; j < i; j++){if(mice[j].size < mice[i].size && dp[i] < dp[j]+1){dp[i] = dp[j]+1;pre[ mice[i].id ] = mice[j].id; //记录路径}}if(maxans < dp[i]){maxans = dp[i];maxid = mice[i].id; //错写成maxid = i,Wa了几次.}}printf("%d\n",maxans);int ans[1010],count = 0;for(int t = maxid; t != -1; t = pre[t]){ans[count++] = t;}for(int i = count-1; i >= 0; i--)printf("%d\n",ans[i]);
}int main()
{int s,w;cnt = 0;while(~scanf("%d %d",&s,&w))mice[++cnt] = (struct node){s,w,cnt};maxans = 0;sort(mice+1,mice+1+cnt);solve();return 0;
}
这篇关于hdu 1160 FatMouse's Speed(最长上升子序列 +记录路径)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
