大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
主题链接:http://acm.hdu.edu.cn/showproblem.php?pid=1160
题意:求体重下降。速度添加的样例最多有多少个
依据体重降序排一下,然后求速度的最长上升子序列 ,经典的LIS问题,记录一下路径
代码例如以下:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 1010; struct cat{ int w,s,id; bool operator < (const struct cat &b) const { return w>b.w; } }c[maxn]; int q[maxn],path[maxn]; int bin_search(int x,int l,int r) { while(l<=r){ int mid=(l+r)>>1; if(c[q[mid]].s<x) l=mid+1; else r=mid-1; } return l; } int main() { //freopen("out.txt","w",stdout); int cnt=0; while(cin>>c[cnt].w>>c[cnt].s) c[cnt].id=cnt+1,cnt++; sort(c,c+cnt); //cout<<"**************"<<endl; //for(int i=0;i<cnt;i++) // cout<<c[i].w<<" "<<c[i].s<<" "<<c[i].id<<endl; //cout<<"**************"<<endl; int len=0; q[len++]=0; path[0]=0; for(int i=1;i<cnt;i++){ if(c[i].s>c[q[len-1]].s){ path[i]=q[len-1]; q[len++]=i; } else{ int idex = bin_search(c[i].s,0,len-1); path[i] = idex ? q[idex-1] : 0; q[idex] = i; } } printf("%d\n",len); printf("%d\n",c[q[len-1]].id); int tmp=q[len-1]; while(--len){ tmp = path[tmp]; printf("%d\n",c[tmp].id); } return 0; } /******* 6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900 *****/
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117192.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...