L2-014列车调度(最长上升子序列LIS)[通俗易懂]

L2-014列车调度(最长上升子序列LIS)[通俗易懂]原题链接最长上升子序列火车站的列车调度铁轨的结构如下图所示。两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有9趟列车,在入口处按照{8,4,2,5,3,9,1,6,7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开,则至少需要多少条平行铁轨用于调度?输入格式:输入第一行给出一个整数N (2 ≤ N ≤10​5​​ ),下一行给出从1到N的整数序号的一个重排列。数字间

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

原题链接

最长上升子序列

火车站的列车调度铁轨的结构如下图所示。

在这里插入图片描述

两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有9趟列车,在入口处按照{8,4,2,5,3,9,1,6,7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开,则至少需要多少条平行铁轨用于调度?

输入格式:
输入第一行给出一个整数N (2 ≤ N ≤10
​5
​​ ),下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。

输出格式:
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

输入样例:

9
8 4 2 5 3 9 1 6 7

输出样例:

4

题解
此题是求用多少个下降段可以分开这段序列,因此可以转化为最长上升子序列

#include<bits/stdc++.h>
#define x first
#define y second
#define send string::nops
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int M = 3 * N;
const int INF = 0x3f3f3f3f;
typedef pair<int,int> PII;
typedef struct Node * pnode;
int a[N];
int line[N],cnt;
int main(){ 
   
    int n;
    cin>>n;
    for(int i = 0;i < n;i ++){ 
   
        cin>>a[i];
    }
    for(int i = 0;i < n;i ++){ 
   
        int pox = upper_bound(line,line + cnt,a[i]) - line;
        line[pox] = a[i];
        if(cnt == pox)cnt ++;
    }
    cout<<cnt<<endl;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168787.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • USB大容量存储设备_usb网卡变成大容量存储设备

    USB大容量存储设备_usb网卡变成大容量存储设备[USB开发]USB大容量存储设备的开发cxl84发表于2008-3-1723:24:00USB是目前在打印机,数字存储设备,输入/输出设备,数码像机,MP3播放器等其他周边设备中得到广泛应用的连接方式。USB设备具有使用方便,速度快,连接灵活,即插即用,总线供电等优点。基于USB接口的大容量存储设备(USBMassStorage)应运而生,目前市场上的这类设备主要有:USB移

  • 运维shel小编(2)

    运维shel小编(2)

  • 安卓天天练练(五)CompoundButton

    安卓天天练练(五)CompoundButtonToggleButton让我想起了从前jQuery还没有取消toggle方法时是怎么偷懒的。。注意:如果LinearLayout,与RelativeLayout不同,必须有orientation。用可视化顶部的横着隔开或者竖着隔开的方形按钮也可以选择,例如android:orientation=”vertical”三目运算符前面和js一样,那个state是不需要额外带括号的按…

  • django的render函数_reverse函数用法

    django的render函数_reverse函数用法reverse函数reverse函数的作用是用来进行URL反转的,接下来我们介绍reverse函数的几种用法之前我们都是通过url来访问视图函数。有时候我们知道这个视图函数,但是想反转回他的url

  • uva 10548 – Find the Right Changes(拓展欧几里得)

    uva 10548 – Find the Right Changes(拓展欧几里得)

  • Java 递归、DFS、回溯

    Java 递归、DFS、回溯DFS/回溯算法如果某问题的解可以由多个步骤得到,而每个步骤都有若干种选择(这些候选方案集可能会依赖之前做出的选择),且可以用递归枚举法实现,则它的工作方式可以用解答树来描述。全排列问题输出数字1~N所能组成的所有全排列publicclassA{/***全排列**@paramargs*/staticVector<Integer>vector=newVector<>();s

发表回复

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

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