一中OJ | #1438 航線設(shè)計(jì)

時限 1000MS/Case 內(nèi)存 64MB/Case

題目描述

有一個國家被一條河劃分為南北兩部分，在南岸和北岸總共有N對城鎮(zhèn)，每一城鎮(zhèn)在對岸都有唯一的友好城鎮(zhèn)。任何兩個城鎮(zhèn)都沒有相同的友好城鎮(zhèn)。每一對友好城鎮(zhèn)都希望有一條航線來往。于是他們向政府提出了申請。由于河終年有霧。政府決定不允許有任兩條航線交叉（如果兩條航線交叉，將有很大機(jī)會撞船）。
你的任務(wù)是寫一個程序來幫政府官員決定他們應(yīng)撥款興建哪些航線以使得沒有出現(xiàn)交叉的航線最多。?

輸入格式

第一行一個整數(shù)N，表示分布在河兩岸的城鎮(zhèn)對數(shù)。接下來的N行每行有兩個由空格分隔的正數(shù)C，D（C、D<=10^9〉，描述每一對友好城鎮(zhèn)沿著河岸與西邊境線的距離，C表示北岸城鎮(zhèn)的距離而D表示南岸城鎮(zhèn)的距離。在河的同一邊，任何兩個城鎮(zhèn)的位置都是不同的。

輸出格式

在安全條件下能夠開通的最大航線數(shù)目。

樣例輸入

7
22 4
2 6
10 3
15 12
9 8
17 17
4 2

樣例輸出

4

數(shù)據(jù)范圍

1<=N<=500000

----------------------------------------------------------

題目分析

將上下兩端看成匹配，假設(shè)有航線A<-->B和航線C<-->D，它們不交叉的條件是AB的不等關(guān)系與CD相同(當(dāng)A<B時C<D 或 當(dāng)A>B時C>D)

那么將每條航線按北端點(diǎn)進(jìn)行排序，在搜索A的時候，A一定是小于A后面的所有元素的，那么這個時候只需要找一個大于C的D即可。

因?yàn)楸倍它c(diǎn)已經(jīng)有序了，那么只需要對南端點(diǎn)的序列找LIS就可以保證一定不會相交啦

----------------------------------------------------------

關(guān)于NlogN找LIS的方法

網(wǎng)上已經(jīng)有無數(shù)篇介紹這個方法的啦，但是還是說一下吧

設(shè)數(shù)組d儲存當(dāng)前的最小字典序的LIS序列

也就是d[i]代表當(dāng)前長度為i的LIS的第i位的最小值

動態(tài)維護(hù)d數(shù)組，假設(shè)當(dāng)前最長長度為ans，那么當(dāng)a[i+1]大于d[ans]的時候把d[ans+1]改成a[i]，表示找到了長度為ans+1的LIS，ans+1

當(dāng)a[i+1]不大于d[ans]的時候二分找a[i+1]能排到什么位置，然后與d[x]替換，即可保證d數(shù)組一定是字典序最小的LIS序列

更詳細(xì)的解釋來自我寫代碼的時候敲的注釋::

/*
設(shè)d[i]為長度為i的LIS的末尾元素的最小值
對d[i]進(jìn)行維護(hù)使得d[i]保持單調(diào)遞增性
設(shè)當(dāng)前DP找到的LIS長度為i，當(dāng)找長度為i+1的LIS的時候就可以使用二分查找來找比d[i]大的最小值
那么如何對一個沒有排序的序列進(jìn)行二分查找呢？這顯然是不現(xiàn)實(shí)的
其實(shí)只需要對d進(jìn)行二分查找，找到的i就是以當(dāng)前a[x]為末尾的LIS長度
此時為了保證d[i]是長度為i的LIS的末尾元素的最小值，對d[i]進(jìn)行更新，d[i]=min(d[i],當(dāng)前數(shù)字)
如果二分查找的結(jié)果是d數(shù)組的末尾+1，說明當(dāng)前數(shù)字可以插入LIS中，再把d[i]更新成當(dāng)前數(shù)字即可

------

特別注意，{d[i] | i>0}的初始值應(yīng)該為inf，這樣可以保證無論如何都可以替換d[i]
*/

----------------------------------------------------------

代碼

#include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <set> #include <queue> #include <stack> #include <vector> #include <map> #define hashsize 1000003 #define inf 0x7f7f7f7f using namespace std; struct node {friend bool operator <(node a,node b){return a.north<b.north;}int north;int south; }line[500005]; int d[500005],a[500005],ans=0,n; int main() {scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d%d",&line[i].north,&line[i].south);sort(line+1,line+1+n);for(int i=1;i<=n;i++) a[i]=line[i].south;for(int i=1;i<=n;i++) d[i]=inf;d[0]=-inf;for(int i=1;i<=n;i++){int p=upper_bound(d+1,d+ans+1,a[i])-d;//當(dāng)p為ans+1時，說明當(dāng)前數(shù)字可以插入LISif(p==ans+1){ans++;d[ans]=a[i];}else d[p]=min(d[p],a[i]);}cout<<ans;return 0; }

總結(jié)

以上是生活随笔為你收集整理的一中OJ #1438 航线设计 | LIS 序列DP | 解题报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。