首页 > 代码库 > hdu1160 LIS变形
hdu1160 LIS变形
题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=1160
题意:两个子序列 一个是升序,一个是降序,求最长的子序列是多大,并输出路径。(答案不唯一)
思路都是一样的,不断的更新当前值,优化之前的值,只不过还要记录一下路径。
代码:(注释应该就可以看得懂了)
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; #define INF 0x3f3f3f3f const int maxn=1e6+5; struct mice { int w,v,r,l; ///分别是体重,速度,位置,她前一个小鼠的位置 } m[maxn]; int dp[maxn]; ///dp代表第i位老鼠的时候,能达到的最大长度 int a[maxn]; ///记录路径 int cmp(mice a,mice b) { if(a.w==b.w) return a.v<b.v; else return a.w>b.w; } int main() { int x,y,k=0; while(scanf("%d%d",&x,&y)==2) { k++; m[k].w=x; m[k].v=y; m[k].r=k; m[k].l=0; } sort(m+1,m+1+k,cmp); memset(dp,0,sizeof(dp)); m[0].w=INF; ///初始化m[0]; m[0].v=0; m[0].r=0; m[0].l=0; int ans=0; dp[0]=0; for(int i=1; i<=k; i++) { for(int j=0; j<i; j++) { if(m[j].w>m[i].w && m[j].v<m[i].v) { if(dp[j]+1>=dp[i]) { dp[i]=dp[j]+1; ///长度+1 m[i].l=j; if(dp[i]>dp[ans]) ans=i; } } } } printf("%d\n",dp[ans]); while(m[ans].l!=0) { printf("%d\n",m[ans].r); ans=m[ans].l; } printf("%d\n",m[ans].r); return 0; }
hdu1160 LIS变形
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。