大家好，又见面了，我是全栈君，今天给大家准备了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
*****/
版权声明：本文博客原创文章，博客，未经同意，不得转载。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/117192.html原文链接：https://javaforall.net
