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)
blank

相关推荐

  • 校验和(Checksum)「建议收藏」

    校验和(Checksum)「建议收藏」校验和(Checksum)PE的可选映像头(IMAGE_OPTION_HEADER)里面,有一个Checksum字段,是该文件的校验和,一般EXE文件可以使0,但一些重要的和系统DLL及驱动文件必须有

  • python网页爬虫代码_python md5加密解密

    python网页爬虫代码_python md5加密解密#!/usr/bin/envpythonimportos,sys,subprocessdefupdate(path):f=open(file,’w’)forroot,dirs,filesinos.walk(path):fornameinfiles:line=os.path.join(root,name)(stdin,stderr)=subprocess.Popen(…

  • nginx设置编码格式utf-8[通俗易懂]

    nginx设置编码格式utf-8[通俗易懂]nginx设置编码格式utf-8在server下配置charsetutf-8;server{listen8000;server_namelocalhost;charsetutf-8;}后台使用tomcat时,get请求参数乱码更改nginx编码格式设置无效需要更改tomcat编…

  • mybatis配置文件位置

    mybatis配置文件位置目录配置文件在resource/mapper文件下项目结构配置文件在java/**/mapper/xml文件夹下项目结构配置总结配置文件在resource/mapper文件下优点:配置文件在resource文件夹下,类文件在Java文件夹下,结构清晰项目结构##配置1、properties文件#配置扫描mybatis.mapper-locations=classpath:mapper/**.xml2、启动类@MapperScan(value=”top.jiug.sa.mapp

    2022年10月29日
  • 组件接口(API)设计指南[4]-通知(Notifications)「建议收藏」

    组件接口(API)设计指南[4]-通知(Notifications)

  • URAL 1146

    URAL 1146题目大意:给出一个N*N的矩阵,每个元素的范围为[-127,+127]。求其所有子矩阵中各元素之和的最大值。TimeLimit:1000MS     MemoryLimit:65536KB     64bitIOFormat:%I64d&%I64u数据规模:N理论基础:无。题目分析:求和问题,用前缀和(每一行)+枚举(对列的起始与终点和行的起始与终点枚举)即

发表回复

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

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