**Chatper 6 (II)**
Alignment是生物序列(如DNA與蛋白質)分析的重要問題，輸入兩個字元序列，我們要將兩序列的字母依照原順序做一個對應，過程中可以將任一序列的某些位置加入空白，以輸入”CTTAACT”與”CGGATCAT”為例，以下是一個可能的alignment (以-表示空白)：
```
CTTAAC-T
CGGATCAT
```
以下也是一個alignment：
```
C---TTAACT
CGGATCA--T
```
alignment的目的是要評估兩序列有多相似，我們會有一個評分機制，以下是一個例子：兩字母相同得8分，相異 -5分，字母與空白對應 -3分。
給定評分機制，輸入兩序列，要計算最大的alignment分數。
Alignment可分為global alignment與local alignment，前者是輸入的序列整個要納入alignment，而後者是兩序列各選取連續的一段來做alignment。
---
##### Q-6-8. Local alignment
輸入兩字串，計算local alignment的最大分數。評分機制為：兩字母相同得8分，相異 -5分，字母與空白對應 -3分。
Time limit: 1秒
輸入格式：第一行與第二行各有一個字串，字串均只由ATCG四個字母組成，長度不超過500。
輸出：Local alignment的最大分數。
範例一輸入：
ATATCTTAACTGG
CGCGGATCATAA
範例一輸出：
43
範例二輸入：
AAAACTGAGGG
GGCTATT
範例二輸出：
21
範例一說明：第一個字串取ATCTTAA，第二個取ATCATAA。
範例二說明：第一個字串取CTGA，第二個取CTA。
---
提示：計算global alignment與LCS很類似，計算local alignment與global的差別在於：可以”昨日種種譬如昨日死”，DP過程中，如果前面的分數不好，可以放棄繼承，此外，最大分數未必出現在最後的位置。
下面一個例題是經典名題0/1-knapsack，經典的原因是他在很多地方都是一個具有代表性的問題。
---
##### P-6-9. 大賣場免費大搬家
你抽中了大賣場的周年慶的抽獎活動，在不超過總重量 $W$ 的限制下，你可任意挑選商品免費帶走。現場一共 $n$ 項商品，每項商品有它的重量與價值，每項商品只可以選或不選，不可以拆開只拿一部份。請計算可以獲得的最大價值總和。
Time limit: 2 秒
輸入格式：第一行有兩個正整數 $n$ 與 $W$。第二行有 $n$ 個正整數，依序代表商品的重量，第三行有 $n$ 個正整數，依序代表對應 $n$ 項商品的價值。同一行數字間以空白隔開。$n \le 100$，$W$ 與各商品重量及價值皆不超過1e4。
輸出：最大價值總和。
範例一輸入：
7 10
3 4 2 3 3 6 5
5 5 2 4 4 5 6
範例一輸出：
14
範例二輸入：
5 14
1 2 3 4 5
3 2 4 4 4
範例二輸出：
15
範例一說明：選擇第1, 2, 4三項，重量為3+4+3=10，價值為5+5+4=14。
範例二說明：選擇第1, 3, 4, 5四項，重量為1+3+4+5=13，價值為3+4+4++4=15。
---
假設每個物品的價值與重量恰好成正比，或是更簡單的說，價值等於重量，這個問題就變成在總重量 $W$ 限制下要裝越重越好，這個簡化版的問題稱為Subset-sum就是我們下一個習題。
其實他更早就出現在我們第一章的Q-1-8，當時是用來介紹$O( 2^n)$的暴搜法，物品數量小，可以產生所有的子集合來檢查。
這個題目在沒有其他條件下，並沒有人發明出真正好的演算法，這裡說好的意思是時間複雜度為多項式而不會跑到指數函數。這一題我們把 $n$ 的範圍放到100，但增加了一個限制條件：$W$ 的範圍不超過1e5，也就是說在 $W$ 不大的狀況下，有一個好的算法，這是這一題的經典之一，也是放在此處的主要目的。
以DP的思維模式，假設我們將子問題定義成 $dp[i]$ 是考慮前 $i$ 個物品的最佳解，我們在設法列出遞迴式時會遭遇到困難，主要因素是加入一個新的物品時，前面找出來的最佳解可能全部改變，例如考慮前5項時，最佳解可能是挑第1與第2件，但是第6項納入考慮時，可能最佳解變成第6與第3,4項。這樣找不到子問題最佳解之間的關係，所以是個失敗的定義。
前面我們說過一個原則，找不出的時候常用的手法就是加條件，也可以說把解進一步分類。我們考慮加入第二個條件：重量。令 $d[i][j]$ 是考慮前 $i$ 項物品且重量不超過 $j$ 的最佳解(最大可以獲得價值)，那麼遞迴式就好列了。
假設第 $i$ 項物品的重量是 $w[i]$，而價值是 $p[i]$，我們分成以下情形：
* $w[i]>j$：也就是根本不可能挑選，所以第 $i$ 項物品有沒有都一樣，
$d[i][j]=d[i-1][j]$。
* $w[i] \le j$，但是選擇不放：跟前一個情形一樣。
* 挑選第 $i$ 項物品：既然已經挑選了第 $i$ 項，那麼前 $i-1$ 項中挑選的重量不超過 $j - w[i]$，因此，
$d[i][j]=p[i]+d[i-1][j-w[i]]$。
最後的答案出現在$d[n][W]$，而邊界條件為：沒有物品或重量限制0的時候的最大價值都是0。整理一下結果：
$$
dp[i][j] = \left\{
\begin{array}{ll}
dp[i-1][j] & \text{ if }w[i]>j \\
\max\Bigg\{
\begin{array}{l}
dp[i-1][j-w[i]]+p[i]\\
dp[i-1][j]
\end{array}
\Bigg\} & \text{otherwise}
\end{array}
\right.
$$
還是有點眼熟，把dp[][]看成一個表格，每一個格子跟上方與左上方的某個格子有關。所以我們依然可以用 $i$ 由小到大，$j$ 由小到大的順序來計算，以下是範例程式，時間複雜度是$O(nW)$，其中 $W$ 是總重限制，它跟之前看到的複雜度只有 $n$ 不一樣，當$W$很大的時候(例如1e20)，這個程式很糟；但如果 $W$ 不大(例如本題1e5)這個程式跑起來要比暴搜好太多了，這個時間複雜度被稱為”偽多項式時間複雜度”(pseudo-polynomial time complexity)。
請留意，物品的index由0開始，程式中 $d$ 有 $n+1$ 列，當$i = 0$時，$d[i-1]$ 會參照到最後一列($d[-1]$)，那值會是0。另外一種寫法是把第0列單獨寫在迴圈之外。
```python=
# 01-knapsack, $O(Wn) space
n,total = [int(x) for x in input().split()]
w = [int(x) for x in input().split()] # weight
p = [int(x) for x in input().split()] # price
# max price of first i items with <= j weight
d = [[0]*(total+1) for i in range(n+1)]
# last row d[n] is d[-1][] = 0 sentinel
for i in range(n):
for j in range(total+1):
if j < w[i]:
d[i][j] = d[i-1][j] # too heavy, discard
else : # choose or not choose
d[i][j] = max(d[i-1][j-w[i]]+p[i], d[i-1][j])
#
print(d[n-1][total])
```
以下的習題是背包問題的退化形式，解法類似，留做習題，這題當然可以用前面介紹過的滾動陣列來節省記憶體，其實它甚至可以只用一維陣列，有興趣的人可以試試看。
---
##### Q-6-10. 置物櫃出租 (APCS201810)
王老先生有一個置物櫃，共有 $M$個相同大小的格子，置物櫃目前已經租給 $n$ 個客戶，第 $i$ 位客戶所租的大小為$f(i)$個格子$(1 \le i \le n)$。目前的承租量總和不超過 $M$，但是現在王老先生自己需要使用 $S$ 個格子的置物櫃，如果剩下的容量不夠，就必須退掉某些客戶的租約。假設每個客戶所租容量只能全退或全不退，而退租第 $i$ 個客戶損失的利益與其所租容量 $f(i)$ 相同，請寫一支程式計算王老先生最小的損失利益，如果不須退租，則損失為0。
Time limit: 4 秒
輸入格式：測試資料有兩行，第一行有三個正整數，依序是 $n$、$M$ 與 $S$，其中 $S \le M$，第二行是 $n$ 個正整數$f(1), f(2), f(3), ..., f(n)$，同一行的數字間以空白隔開。$1 \le n \le 100$，$M \le 1e5$
輸出：輸出王老先生最小的損失利益。
範例一輸入：
3 10 6
4 4 1
範例一輸出：
5
範例二輸入：
5 20 14
8 2 7 2 1
範例二輸出：
15
範例一說明：總共容量10，已出租9，剩下1，需要6，最少退租4+1=5。
範例二說明：總共容量20，已出租20，剩下0，需要14，最少退租8+7=15。
---
### 1D1D
1D1D的DP是指有$O(n)$個子問題(狀態)，但每一個子問題的計算需要$O(n)$個子問題的結果，也就是說一個狀態會牽涉$O(n)$個前置狀態。如果直接的計算，時間複雜度就是$O(n^2)$。
不過很多1D1D問題的計算都會利用資料結構或問題的特性來降低複雜度，也就是因為如此，1D1D的DP出現在競賽或考試場合的題目通常比前面看到的1D0D或2D0D的題目來得難，有些題目甚至可以說非常難。以下我們挑選一些適合這份教材難度的典型題目。
我們先從簡單的開始，這一個例題我們在第一章說明遞迴時曾經拿出來舉例，這是一個非常有名的數，興趣的可以去網路搜尋一下，這裡我們只關心如何計算。
---
##### P-6-11. Catalan number
Catalan number的遞迴式定義：
$C_0=1$ and $C_n= \sum_{i=0}^{n-1)} C_i\times C_{n-1-i}$ for $n\ge 1$。
計算$C_n$ 除以P的餘數，P=1e9+9。
Time limit: 1秒
輸入格式：輸入一個非負整數$n$，$n < 1000$。
輸出：$C_n$ 除以P的餘數。
範例一輸入：
3
範例一輸出：
5
範例二輸入：
20
範例二輸出：
564120366
---
題目中直接給了Catalan number的遞迴定義，要計算它的第 $n$ 項，因為數字很大，所以要求輸出除以 $P$ 的餘數。遞迴式中涉及的運算只有加法與乘法，雖然本題的數字不至於讓Python溢位，但建議每次運算完都取一次餘數，否則如果數字更大一點就有可能在過程中溢位，而且太大數字的計算也比較慢。雖然這一題正常的DP寫法就很容易，以下我們用它來示範top-down的寫法。
以下是範例程式。Top-down DP的重點是準備一個 $memo$ 來記錄算過的答案，主程式第11行我們將 $memo$ 初設均為 -1 來表示沒算過，接著依照定義 $memo[0]=1$，然後就呼叫遞迴函數 $cat(n)$ 計算與輸出答案。
函數 $cat(n)$ 一進入時先檢查 $memo[n]$ 是否大於等於0，若是，表示曾經算過，直接回傳答案；否則，依照定義在第5 ~ 7行利用遞迴計算，最後在第9行回傳，且回傳前先存入 $memo[n]$ 中。如果不使用memo的技術，純遞迴會非常耗時間，但如果這樣寫，時間複雜度跟bottom-up的一樣都是$O(n^2)$，因為總共有 $n$ 個格子要算，每一個花費$O(n)$的時間。
```python=
# P-6-11 Catalan number // top-down, mod every time
n = int(input())
def cat(n):
if memo[n] >= 0: return memo[n]
s = 0
for i in range(n):
s = (s+cat(i)*cat(n-1-i))%p
memo[n] = s
return s
# main()
memo = [-1]*(n+1)
memo[0] = 1 # initial condition
p = 10**9+9
print(cat(n))
```
所附檔案中還有兩支範例程式，一支是正常bottom-up的寫法，另外一支是運用數學解，Catalan number在數學上可以解出來，第 $n$ 項的值是$C(2n,n)/(n+1)$，其中$C(2n,n)$是 $2n$ 個相異物取 $n$ 個的組合數，所以我們可以直接用公式計算它的值。Python 在 3.8版之後有math.comb可以直接算組合數，但數字太大的話仍不可直接使用。如果我們要自己根據組合公式自己算，因為中間涉及除法，而模P的運算不可以直接使用除法，需要轉換成乘以除數的模反元素。計算Catalan number是解遞迴關係(差分方程)一個經典例子，但這些都超過中學生的數學範圍，在離散數學的課程中可以學到。上面這段補充說明只是給有興趣的人參考，如果覺得困難，你可以略過。
下面這一題是P-6-2的推廣，留做習題。
---
##### Q-6-12. 楊鐵心做1休K
楊鐵心帶著義女穆念慈做武術表演已經很久了，因為有些表演(例如胸口碎大石)實在很傷身體，所以現在每次表演完都要休息養傷。他接到許多的邀約，每天均有一場。每一場表演都可以得到某些金額的報酬，但是每次表演完至少要休息 $K$ 天，請你協助他決定應該接受那些表演以得到最大的報酬。
Time limit: 1秒
輸入格式：第一行有兩個正整數 $n$ 與 $K$。第二行有 $n$ 個正整數，依序代表第1天開始每天邀約報酬，數字間以空白隔開。$K < n \le 1e5$，每天酬勞不超過10000。
輸出：最大可能獲得的總酬勞。
範例一輸入：
5 1
1 2 3 1 5
範例一輸出：
9
範例二輸入：
8 3
2 1 1 7 3 2 9 2
範例二輸出：
11
範例一說明：挑選1+3+5=9。
範例二說明：挑選2+9=11。請注意，如果挑了9，就不可以挑7，兩者只隔2天。
---
下一題是P-6-3的推廣型。
---
##### P-6-13. 周伯通的基地台 (@@)
周伯通開了一家通訊大廠並以他的名字命名，就叫做伯通公司，也有不少人弄錯了稱為博通。周伯通標下了一個政府標案，要在一條長長的大街架設基地台，長街被劃分成 $n$ 個區段。在第 $i$ 個區段架設基地台的話，需要成本$c[i]$，而可以服務第 $i-k$ 到第 $i+k$ 的區段(超出範圍可忽略)。現在輸入 $k$，要選一些區段架設基地台，以便每一個區段都可以被服務到，請計算最少的總成本。
Time limit: 1秒
輸入格式：第一行有兩個正整數 $n$ 與 $k$。第二行有 $n$ 個正整數，依序代表$c[0], c[1], …, c[n-1]$，數字間以空白隔開。$k < n \le 2e5$，每處成本不超過1000。
輸出：最小總成本。
範例一輸入：
5 1
1 2 3 1 5
範例一輸出：
2
範例二輸入：
8 2
2 1 1 7 3 2 9 2
範例二輸出：
3
範例一說明：挑選1+1=2。
範例二說明：挑選1+2=3。
---
若 $k=1$，這一題就是P-6-3。令 $dp(i)$ 表示可以服務 $i$ 之前的所有位置而最後一個站架在 $i$ 最小成本，因為與前一站的距離不可超過 $2k+1$，所以前一站必然在$[i-2k-1, i-1]$，我們可以得到
$dp(i)=c[i]+\min\{p(j): i-2k-2 < j < i\}$ for $i > k+1$; and
$dp(i)=c[i]$ for $i \le k+1$。
這裡假設超出範圍的 $dp(i)$ 為無窮大。最後的解在$\min\{dp(i): n-k \le i \le n\}$。如果直接做，需要 $O(kn)$ 的時間，資料夾中有一個這樣的範例程式，它只能在時限內跑出比較小的測資，有興趣者請自行參考，這裡就不說明了。
要改善時間，我們要設法很快的求得區間最小值，有一些比較高階的資料結構可以每次求的區間最小值(RMQ, range minimum query)，但那超出了這份講義目前要講的範圍。
在P-3-8例題中，我們曾經處理過這樣的問題：在一個滑動的視窗中每次可以找出最小值，所以這一題要綜合之前學過的這個技術，算是比較困難的題目。
回顧P-3-8的做法，基本上我們啟用一個deque(雙向佇列)，這一題只會往前滑動，所以自製也容易。在deque中我們只須要維護一個遞增序列，因為後面如果有碰到比較小的，前面的就沒用了。所以deque的前端就是區間最小值，每回合先檢查前端是否已出界，然後把新的從後端放進deque並且移除任何大於它的資料。以下是不使用Python deque物件的寫法。
```python=
# P-6-13 K-dominating set of a path, O(n)
# dp[i]= min cost to cover [1..i] and choosing i
# dp[i] = c[i]+min{dp[j]: j>i-2k-2}; and dp[i]=c[i] for i<=k
# using monotonic deque
n,k = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
dp = [0]*n
# deque, maintain increasing subsequence
minq = [] # (dp-value,index)
head = 0 # head of minq
for i,cost in enumerate(c):
if minq and minq[head][1] < i-k-k-1:
head += 1 # remove out of date
# find dp[i]
if i <= k:
dp[i] = cost
else: # min at head
dp[i] = cost+minq[head][0]
while minq and minq[-1][0] >= dp[i]:
minq.pop()
minq.append((dp[i],i))
#
# find answer at min(dp[n-k-1:])
print(min(dp[n-k-1:]))
```
資料夾中也有一份用deque()物件的範例程式，寫法十分相似，有興趣的讀者請自行參考。
因為我們之前也教了PQ(priority_queue)，這一題因為區間一直往右滑動，所以區間的最小值也可以用PQ來做，不過前兩個寫法的複雜度只有$O(n)$，而使用PQ是$O(n\log n)$。使用PQ來做區間最小值時有一個問題，就是如何刪除PQ內那些因為距離太遠的值呢？我們可以秉持偷懶的原則也就是不必積極的去刪除它們，等到它們從PQ出來時加以檢查即可。
以下是範例程式。程式與使用deque的方法非常相似，差異在第11行進入迴圈歷遍時，我們對於PQ中的最小值用一個while迴圈刪除所有已經超過區間的資料。此外在迴圈結尾時，我們沒有像deque由後往前刪除資料的動作。
```python=
# P-6-13 K-dominating set of a path, O(nlogn)
# dp[i]= min cost to cover [1..i] and choosing i
# dp[i] = c[i]+min{dp[j]: j>i-2k-2}; and dp[i]=c[i] for i<=k
import heapq # using pq
n,k = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
dp = [0]*n
# deque, maintain increasing subsequence
minq = [] # (dp-value,index) min-heap
for i,cost in enumerate(c):
while minq and minq[0][1] < i-k-k-1:
heapq.heappop(minq) # remove out of date
# find dp[i]
if i <= k:
dp[i] = cost
else: # min at head
dp[i] = cost+minq[0][0]
heapq.heappush(minq, (dp[i],i))
#
# find answer at min(dp[n-k-1:])
print(min(dp[n-k-1:]))
```
下一題是P-4-12.(一次買賣)的推廣型。
---
##### Q-6-14. K次買賣 (106高中全國賽subtask)
某商品在某個時期每一天的價格是$p[1], p[2],…,p[n]$。假設只能先買後賣，且賣了之後才能再買，請計算買賣 $K$ 次的最大獲利總價差，允許當天買賣，也就是不超過 $K$ 次的買賣。
Time limit: 2秒
輸入格式：第一行是正整數 $n$ 與 $K$，第二行有 $n$ 個正整數 $p[1], p[2],…,p[n]$。$n$ 不超過1e4，$K<100$，商品價格皆不超過1e7。
輸出：買賣不超過 $K$ 次的最大總價差。
範例一輸入：
5 1
3 5 1 4 0
範例一輸出：
3
範例二輸入：
7 2
1 3 7 5 1 4 0
範例二輸出：
9
範例一說明：買1賣4。
範例二說明：買1賣7，再買1賣4。
---
註：本題有效率更高的解法，但難度太高，這裡只要求$O(kn)$的解。
Q-6-14提示：令$f(i,j)$為在第 $j$ 天之內完成不超過 $i$ 次買賣的最大獲利，則
$g(i,j) = \max\{p[j]-p[t]+f(i-1,t-1): \text{ for all } t<j\}$
是在第 $j$ 天最後賣出的最大獲利，顯然算出 $g$ 之後再取一次的prefix maximum就可以得到 $f$。運用一個 $i$ 迴圈跑 $k$ 次，在 $i$-迴圈內，對每一個 $j$ 點找出對應的$t$ 就可以算出$g()$與$f()$了。
至於計算$g(i,j)$時要如何有效的找到轉移點 $t$呢？我們可觀察
$g(i,j) = p[j] - \min_{t<j}\{ p[t] - f(i-1,t-1)\}$
其中那個min其實只是個prefix min。
從實際意義上來看，該min項次就是在第 $j$ 天之前買入且扣除之前做至多 $i-1$ 次交易賺的錢的成本。
---
##### P-6-15. 一覽衆山小
所謂「會當凌絕頂，一覽衆山小。」很多人都想爬到高處，為的是將群山看小，但是登高必自卑，行遠必自邇，最好是一步一步逐步往上，妄想一步登天的人往往摔的慘重。小說與遊戲中出現的人物往往都是越晚出現越厲害，現在已知所有人物的戰力與出場順序，想要找出依照出場順序而且戰力逐步上升的人物序列，請你計算滿足這樣要求的序列的最大可能長度。
Time limit: 3秒
輸入格式：第一行有一個正整數 $n$ 代表出場的人物數。第二行有 $n$ 個非負整數，是依出場順序的每一位人物的戰力，數字間以空白隔開。$n \le 2e5$，戰力值不超過1e8。
輸出：出場順序與戰力皆遞增的序列的最大可能長度。
範例一輸入：
8
2 4 1 3 6 4 6 9
範例一輸出：
5
範例二輸入：
5
5 4 3 2 1
範例二輸出：
1
範例一說明：可以挑選子序列(1,3,4,6,9)，長度為5。
範例二說明：輸入是個遞減序列，找不到長度大於1的遞增子序列。
---
一個序列的子序列是指可以任意挑選某些成員，但是不可以交換他們的前後順序，也可以說是刪除某些元素。本題是要在一個數列中找到一個最長的遞增子序列，所以這個問題被稱為**LIS (longest Increasing subsequence)**。這算是一個經典的1D1D的DP，因為不會太困難但是又需要一些技巧。
假設序列是$S[1:n+1]$，從DP的思維開始想，我們定義 $lis(i)$是以第 $i$ 點結束的最長LIS長度，因為前一點一定要比$S[i]$小，所以很容易可以寫出遞迴式，為了方便起見，我們在序列前方加一個 $-1$，這樣便不需要初始條件了：
$lis(i)=\max\{lis(j)+1: j<i \text{ and }S[j]<S[i]\}$。
如果直接實作這個遞迴式，顯然需要$O(n^2)$，因為每個 $i$ 要往前搜尋所有它前面的點。考慮有那些沒有用的計算，假設我們已經做到第 $i$ 個點。對於 $j<i$，若$S[i]\le S[j]$ 而 $lis(i)\ge lis(j)$，也就是 $S[i]$ 是比較小的結尾但是有比較長的LIS，那麼 $j$ 顯然是沒有用的，因為可以接在$S[j]$後面的一定也可以接在$S[i]$後面，而接在$S[i]$後面可以得比較好的結果。如果我們刪除那些沒有用的子問題結果，會剩下甚麼呢？
每一種可能的長度只會有一個點被留下來，lis長度為 $L$ 而被留下來的就是「長度 $L$ 的最小可能結尾」。如果我們將這個資料存放在一個陣列 $last[]$，這個陣列的元素是單調遞增的，在第 $i$ 個回合計算 $lis(i)$ 時，我們搜尋找到$L=\max\{j: last[j]<S[i]\}$，於是我們得到$lis(i)=L+1$，最後我們要將$lis(i)$的資料納入，也就是說 $L+1$ 的長度多一個可能結尾是 $S[i]$，因此$last[L+1]=min(last[L+1],S[i])$。
請稍等，還記得 $L$ 是怎麼來的嗎？$L$ 是小於 $S[i]$ 的最大的那一個 $last[]$，也就是說除非 $L$ 是 $last[]$ 的最後一個元素，否則 $last[L+1]\ge S[i]$，因此根本不必多做一次比較。
整理一下上面說明的結論，求LIS長度的演算法：
```python
# last[i]將紀錄長度為i的最小結尾，前方設一個 -1
last = [-1] # last[0]=-oo, 誰都可以接
for v in S: # 歷遍每一個數字 s[i]=v
找到最後一個 last[j] < v # 最後一個可以接的
以 v 結尾的最大LIS長度是 j+1
紀錄 last[j+1] = v
last的長度減一即是LIS長度，減一是扣除原來放的 -1
```
以下的範例程式是直接根據這樣的思考寫的，推論的過程也許不簡單，但最後的程式卻很簡潔。雖然比$O(n^2)$好，但是還是不太好，因為時間複雜度其實是$O(nL)$，其中 $L$ 是LIS的長度，也就是$last[]$的長度，在最壞的狀況還是$O(n^2)$。
```python=
# P-6-15 LIS O(nL), L is the length, linear search
n = int(input())
s = [int(x) for x in input().split()]
last = [-1] # last[i]=the min end of length i
# last will be increasing
for v in s:
r = 0 # find the max last[r] < v
while r < len(last) and last[r] < v:
r += 1
if r == len(last):
last.append(v)
else:
last[r] = v
#
print(len(last)-1)
```
記得 $last$ 是個單調遞增的陣列嗎？長度越長的結尾越大，既然是單調陣列當然就可以二分搜了，二分搜可以用bisect，如果還不熟也可以自己寫，建議用我們第二章介紹的一路往前跳的方式而避免使用左右轉頭搜的方式。以下的範例程式中，我們把兩種方法寫在同一個程式中以供參考，時間複雜度都是$O(n\log L)$。
```python=
# P-6-15 LIS O(nlogn), binary search, self-made
#import bisect
n = int(input())
s = [int(x) for x in input().split()]
last = [-1] # last[i]=the min end of length i
# last will be increasing
for v in s:
# r = bisect.bisect_left(last,v) the first last[r] >= v
# self-made binary search
r = 0
jump = len(last)//2
while jump:
while r+jump<len(last) and last[r+jump]<v:
r += jump
jump >>= 1
# r is max last[r]<v
if r == len(last)-1:
last.append(v)
else:
last[r+1] = v
#
print(len(last)-1)
```
以下也是個經典例題，它是P-4-4的加權版本。
---
##### P-6-16. 山寨華山論劍
自從華山論劍聲名大噪之後，很多人都想參加，但20年辦一次實在太久了，五輪奧運都跑5趟了，於是各地都紛紛舉辦華山論劍，往往同一天就有很多場。每一場都有自己的開始時間與結束時間，參加者必須全程在場，所以兩場的時間如果有重疊就不能同時參加。令狐沖本來想參加最多場來盡速累積經驗值，但後來他發現有很多場次能獲得的經驗值很少，參加了反而浪費時間，現在要請你幫忙計算最多可以得到的經驗值總和。
請注意，所挑選活動必須完全不重疊，兩場活動只在端點重疊也是不可以同時參加的，也就是說前一場的結束時間必須小於下一場的開始時間。
Time limit: 4 秒
輸入格式：第一行是一個正整數 $n$，代表一共舉辦了 $n$ 場華山論劍，接下來 $n$ 行，每行有三個非負整數 $s$、$t$ 與 $e$，代表這場活動時間區間是$[s,t]$，而可以得到的經驗值是 $e$，兩數字間以空白間格。$n$ 不超過1e5，$s < t < 1e9$，答案不超過1e9。
輸出：最大可能經驗值總和。
範例一輸入：
3
1 2 1
2 3 3
3 4 1
範例一輸出：
3
範例二輸入：
3
1 2 2
2 3 3
3 4 2
範例二輸出：
4
範例一說明：挑選[2,3]，得到經驗值3。
範例二說明：挑選[1,2]與[3,4]，得到經驗值2+2=4。
---
每一場華山論劍(活動)看成一個線段，每個線段除了有起點(左端)與終點(右端)之外，還有一個權重。問題是要挑選權重總和最大且互相不重疊的線段，這個問題也稱為 **weighted activity selection problem**，如果權重都一樣，就是要挑選最多活動，那就是第四章的P-4-4，沒權重的時候是用貪心法則來求解，挑選最早結束的活動就對了，但是在加權版本時，範例一告訴你，挑最早結束的是錯的，範例二告訴你，挑權重最大的也是錯的。
放棄貪心來試試DP。假設線段放在$s[\ ]$中，先讓線段依照右端排序，假設第 $i$ 個線段的區間是 $[L[i], R[i]]$，權重是 $w[i]$。定義 $dp[i]$ 是前 $i$ 個線段的最佳解(最大權重和)。
第 $i$ 個線段可能挑或不挑，不挑的話，很簡單$dp[i]=dp[i-1]$；如果挑呢？跟它重疊的都不能挑，也就是說右端落在 $s[i]$ 範圍內的線段都要剔除，根據 $dp[i]$ 的定義，我們暫且不需要管 $i+1$ 以後的線段。剔除了右端落在 $s[i]$ 範圍的線段就是右端在 $L[i]$之前的線段，也就是
$\max\{dp[j]: R[j] < L[i]\}$。
因為$dp[]$顯然是非下降的，所以我們要找的 $dp[j]$ 就是滿足右端小於 $L[i]$ 的最大編號 $j$。整理一下我們的遞迴式，選或不選i，兩者挑最大：
$dp[i]= \max\{dp[i-1], w[i]+dp[j]\}$，其中 $j=\max\{x: R[x] < L[i]\}$。
從狀態轉移的角度來看，$i$ 的前置狀態有兩個，一個是 $i-1$ (不選 $i$)，另外一個就是在它開始之前最後一個結束的線段(選 $i$)，這樣看其實不難理解，當然，要找到 $j$ 需要一點技術。
先提出根據上面的分析後的天真作法，排序後一一尋找，雖然說天真但也不太單純，我們需要排序一個三個欄位的資料，因為要以右端排序，我們將右端放在第一個欄位，$seg$ 的內容是(右端,左端,權重)的tuple。我們並且在最前方放了一個假的哨兵，讓每一場活動都找得到前一場。排序後以一個 $i$ 迴圈每次計算 $dp[i]$，其中以一個 $j$ 迴圈來找到 $i$ 開始前的最後一個線段，複雜度$O(n^2)$。
```python=
# Weighted activity selection problem, $O( n^2) method
# overlap at endpoint is not allowed
# dp[i] is the max for interval until right(i), sorted by right
# dp[i]=max{dp[i-1], dp[j]+w[i]}, j is the max right <left(i)
n = int(input())
seg = [(-1,-1,0)] # sentinel
for i in range(n): #(right,left,w)
left,right,w = [int(x) for x in input().split()]
seg.append((right,left,w))
seg.sort() # sort by right
dp = [0]*(n+1) # dp[0] is sentinel
for i in range(1,n+1):
# linear search largest j< left[i]
j = i-1
while seg[j][0] >= seg[i][1]: # always found (sentinel)
j -= 1
dp[i] = max(dp[i-1], dp[j]+seg[i][2])
#
print(dp[n])
```
因為右端是經過排序的，當然應該用二分搜比較有效率。以下是自己寫二分搜的範例程式。
```python=
# Weighted activity selection problem, O(nlogn)
# overlap at endpoint is not allowed
# dp[i] is the max for interval until right(i), sorted by right
# dp[i]=max{dp[i-1], dp[j]+w[i]}, j is the max right <left(i)
#import bisect
n = int(input())
seg = [(-1,-1,0)] # sentinel
for i in range(n): #(right,left,w)
left,right,w = [int(x) for x in input().split()]
seg.append((right,left,w))
seg.sort() # sort by right
dp = [0]*(n+1) # dp[0] is sentinel
for i in range(1,n+1):
# binary search largest j< left[i]
#j = bisect.bisect_left(seg, (seg[i][1],))-1
j = 0
jump = i//2
while jump:
while j+jump<i and seg[j+jump][0]<seg[i][1]:
j += jump
jump >>= 1
#
dp[i] = max(dp[i-1], dp[j]+seg[i][2])
#
print(dp[n])
```
當然二分搜也可以呼叫bisect，但是要注意比較的對象是tuple，範例程式中有這種寫法，提供有興趣的人參考，這裡就不多說明了。
**End of Chapter 6 (II)**
續接 [AP325-Python 第6章 動態規劃 (III)](/woskEZuIThiSFMC-k__SbA)
Sign in with Wallet
Connect another wallet