HDU1160(LIS)

HDU1160(LIS)

大家好,又见面了,我是全栈君,今天给大家准备了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账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号