首页 > 代码库 > Uva 10131 Is Bigger Smarter? (LIS,打印路径)
Uva 10131 Is Bigger Smarter? (LIS,打印路径)
链接:UVa 10131
题意:给定若干大象的体重及智商值,求满足大象体重严格递增,智商严格递减的序列的最大个数,
并打印任意一组取得最大值的序列的大象编号
分析:这个是LIS的应用,只不过判断条件有两个,可以先对大象的体重排序,但是要打印路径,
那就必须得回溯求路径,可以直接逆序循环求,当然递归也是一个好的选择
#include<cstdio> #include<algorithm> using namespace std; struct stu { int size,iq,id; }a[1005]; int dp[1005],path[1005],m; int cmp(struct stu a,struct stu b) { if(a.size!=b.size) return a.size<b.size; return a.iq>b.iq; } void back_path1(int i) { if(path[i]!=i) back_path1(path[i]); printf("%d\n",a[i].id); } void back_path2(int i) { if(m--){ back_path2(path[i]); printf("%d\n",a[i].id); } } int main() { int i=1,j,n,k,b[1005]; while(scanf("%d%d",&a[i].size,&a[i].iq)!=EOF){ a[i].id=i; i++; } n=i-1; sort(a+1,a+n+1,cmp); for(i=1;i<=n;i++){ dp[i]=1; path[i]=i; for(j=1;j<i;j++) if(a[j].size<a[i].size&&a[j].iq>a[i].iq&&dp[j]+1>dp[i]){ dp[i]=dp[j]+1; path[i]=j; } } k=1; for(i=2;i<=n;i++) if(dp[i]>dp[k]) k=i; m=dp[k]; printf("%d\n",m); b[1]=a[k].id; i=2; for(j=k;j>=1;j--) //直接逆序循环求路径 if(a[j].size<a[k].size&&a[j].iq>a[k].iq&&dp[k]==dp[j]+1){ b[i++]=a[j].id; dp[k]--; } for(j=i-1;j>=1;j--) printf("%d\n",b[j]); //back_path1(k); //可以用两种递归求路径 //back_path2(k); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。