首页 > 代码库 > uva--10131Is Bigger Smarter? +dp
uva--10131Is Bigger Smarter? +dp
题意:
有人说大象越重就越聪明,为了推翻的它的结论,给你一组大象的体重和智商的数组,你需要找出一组最长的随着体重增加智商下降的序列。
思路:
按照体重排一下序,然后就变成求一个智商最长下降子序列的问题了。
代码如下:
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; typedef struct { int w,s; int id; }P; P p[1100]; int cmp(P p1,P p2) { return p1.w<p2.w; } int fa[1100],max1=-1; void print(int i) { if(max1--) { print(fa[i]); printf("%d\n",p[i].id); } } int main() { int i,j,x,y,n=1; while(scanf("%d%d",&x,&y)!=EOF) { p[n].w=x; p[n].s=y; p[n].id=n; n++; } sort(p+1,p+n,cmp); int dp[1100]; memset(fa,-1,sizeof(fa)); for(i=1;i<n;i++) dp[i]=1; for(i=1;i<n;i++) for(j=1;j<i;j++) { if(p[i].s<p[j].s&&dp[i]<dp[j]+1) { dp[i]=dp[j]+1; fa[i]=j; } } int t; for(i=1;i<n;i++) if(dp[i]>max1) max1=dp[i],t=i; printf("%d\n",max1); print(t); return 0; }
uva--10131Is Bigger Smarter? +dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。