PTA列车调度

PTA列车调度

十月 27, 2020

7-10 列车调度

  • 题意

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

  • 题解

要想得到最少的调度序列，

那就要找出最少的下降序列的个数。拿样例来说：有如下四个下降序列

8 4 2 1

5 3

9 6

7

根据Dilworth定理：某序列的最小的下降序列的个数等于它最长上升子序列的长度。

于是用二分栈优化dp求最长上升子序列

代码实现似乎像用栈模拟，反过来像用栈模拟可以nlogn求解最长上升子序列

LIS最长上升子序列 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
#include <time.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
#define P pair<ll,ll>
const int Max=1e5+5;
const int Mod=998244353;
const int inf=0x3f3f3f3f;
#define random(x) (rand()%x)

int arr[Max],st[Max];
int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        st[i]=inf;
    }
    int need=0;
    for(int i=0;i<n;i++){
        int pos=lower_bound(st,st+n,arr[i])-st;
        st[pos]=arr[i];
        need=max(need,pos+1);
    }
    cout<<need<<endl;
}