首页 > 代码库 > hdu1160(最长上升子序列)
hdu1160(最长上升子序列)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1160
题意:给定一些小猫的属性:体重和速度。然后求某些猫顺序的排列,使得体重上升,速度下降,这样的排列尽量长。
分析:主要将速度按从大到小排序,然后对体重求最长上升子序列即可,这里因为要记录路径,所以只能O(n^2)求解。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 1<<30#define N 2010using namespace std;struct node{ int w,s,num; bool operator<(const node a)const { return (s>a.s||(s==a.s&&w<a.w)); }}t[1010];int dp[1010],path[1010];void print(int x)//输出路径{ if(path[x]==-1) { printf("%d\n",x); return; } print(path[x]); printf("%d\n",x);}int main(){ int n=0; // freopen("in.txt","r",stdin); while(scanf("%d%d",&t[n].w,&t[n].s)!=EOF)t[n].num=n+1,n++; sort(t,t+n); memset(dp,0,sizeof(dp)); memset(path,-1,sizeof(path)); int mx=0,id; for(int i=0;i<n;i++) { dp[i]=1; for(int j=0;j<i;j++) if(t[j].w<t[i].w&&dp[i]<=dp[j]+1) { dp[i]=dp[j]+1; path[t[i].num]=t[j].num; } if(dp[i]>mx) { mx=dp[i]; id=t[i].num; } } printf("%d\n",mx); print(id);}
hdu1160(最长上升子序列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。