L2-014. 列车调度(Dilworth定理)
2024-09-05 01:02:38
火车站的列车调度铁轨的结构如下图所示。
Figure
两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有9趟列车,在入口处按照{8,4,2,5,3,9,1,6,7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开,则至少需要多少条平行铁轨用于调度?
输入格式:
输入第一行给出一个整数N (2 <= N <= 105),下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。
输出格式:
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。
输入样例:
9
8 4 2 5 3 9 1 6 7
输出样例:
4
//Dilworth定理最小反链划分 == 最长链
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
using namespace std; set<int> S;
int main(){
int n, u;
cin >> n;
while(n --){
cin >> u;
if(S.size() && *(S.rbegin()) > u)
S.erase(*(S.upper_bound(u))); S.insert(u);
}
cout << S.size() << endl;
}
最新文章
- JavaScript中的作用域
- JAVA Builder模式构建MAP/LIST的示例
- 通过beego快速创建一个Restful风格API项目及API文档自动化
- 如何创建一个客户端回调:js获得服务端的内容?
- 项目中遇到的 linq datatable select
- 安装 tomat
- iOS动画——弹窗动画(pop动画)
- 控制点:ControlPoint
- centos6.4下没有heartbeat包解决办法
- TComponent,TControl,TWinControl,TGraphic的DefineProperties赏析与说明(不懂)
- 转:web_custom_request 函数
- Android 中基于 Binder的进程间通信
- Description has only two Sentences(欧拉定理 +快速幂+分解质因数)
- SOFA 源码分析 — 扩展机制
- 【English】十四、英语
- PHP连接MySQL数据库的三种方式(mysql、mysqli、pdo)
- 移动Web UI库(H5框架)
- 解决kali linux 开启ssh服务后连接不上的问题
- Java中通过Class类获取Class对象的方法详解
- Hdu3829 Cat VS Dog(最大独立点集)
热门文章
- MySQL_(Java)使用JDBC向数据库中删除(delete)数据
- HDU 5806 NanoApe Loves Sequence Ⅱ ——(尺取法)
- hive连接hbase
- sqoop数据导出
- Linux 如何查看端口与进程占用情况
- LeetCode 80. 删除排序数组中的重复项 II(Remove Duplicates from Sorted Array II)
- window7上爬虫框架Scrapy的安装 --错误分析lxml
- 极光推送报错time_to_live value should be a non-negative integertime_to_live value should be a non-negative integer
- sql_profile 固定SQL执行计划
- Spring Data JPA 介绍