uva 10131 Is Bigger Smarter?

本文主要是介绍uva 10131 Is Bigger Smarter?，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给你n对数（ai,bi），在ai升序排好的情况情况下，输出最长下降子序列。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1005;
struct node
{int x,y,num;
}ele[N];
bool cmp(const node &e1,const node &e2)
{return e1.x<e2.x;
}
int dp[N];
int main()
{int cnt=0,ans=0,pos,i;while(scanf("%d%d",&ele[cnt].x,&ele[cnt].y)!=EOF){dp[cnt]=1;ele[cnt].num=cnt+1;cnt++;}sort(ele,ele+cnt,cmp);for(i=cnt-2;i>=0;i--){for(int j=cnt-1;j>i;j--){if(ele[i].y>ele[j].y&&ele[i].x<ele[j].x){dp[i]=max(dp[i],dp[j]+1);if(dp[i]>ans){ans=dp[i];pos=i;}}}}printf("%d\n",ans);while(pos<cnt){bool flag=false;printf("%d\n",ele[pos].num);for(i=pos+1;i<cnt;i++){if(dp[i]+1==dp[pos]&&ele[pos].y>ele[i].y){flag=true;pos=i;break;}}if(!flag) break;}return 0;
}

这篇关于uva 10131 Is Bigger Smarter?的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---