###### tags: `選修` # AP325 練習題單 + [AP325講義(中正大學 吳邦一教授)](https://drive.google.com/drive/mobile/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m?usp=sharing) + [APCS實作題檢測(Facebook)](https://www.facebook.com/groups/359446638362710) + [中一中](https://judge.tcirc.tw/)、[惠文高中](https://judge.hwsh.tc.edu.tw/) + 以下為吳邦一教授 AP325 內容整理。 <br/> ## ○、預備知識(自行閱讀) **其它補充** ### 1. STL + [從零到一：那些演算法競賽會用到的基礎語法](https://emanlaicepsa.github.io/2020/10/21/0-index/) + pair - [a915. 二维点排序](https://zerojudge.tw/ShowProblem?problemid=a915) - (Greedy) [f627. 1. 礦砂採集](https://zerojudge.tw/ShowProblem?problemid=f627) - (map) [b563. 3.魔法學校交換生問題](https://zerojudge.tw/ShowProblem?problemid=b563) + set - [f607. 3. 切割費用](https://zerojudge.tw/ShowProblem?problemid=f607) - (multiset) [c421. pA 雲端列印](https://zerojudge.tw/ShowProblem?problemid=c421) - [j608. 4. 機器出租](https://zerojudge.tw/ShowProblem?problemid=j608) + map - [a135. 12250 - Language Detection](https://zerojudge.tw/ShowProblem?problemid=a135) - (狀態壓縮、位元運算) [e288. 互補CP](https://zerojudge.tw/ShowProblem?problemid=e288) ### 2. 枚舉 + [c435. MAX ! MAX ! MAX !](https://zerojudge.tw/ShowProblem?problemid=c435) + (狀態壓縮) [c460. 3. 軍隊部署](https://zerojudge.tw/ShowProblem?problemid=c460) ### 3. 前綴和 & 差分 + 『前綴和』為陣列前 n 項的和，可以快速計算區間 $[l, r]$ 的和。 預處理前綴和 $S_i=S_{i-1} + A_i$，則區間 $[l, r] \ 的總和 = S_r \ – \ S_{l-1}$。 例如：A=[1, 5, 3, 6, 2, 4]，前缀和數列 S=[1, 6, 9, 15, 17, 21]， A[1]~A[3]的和(5+3+6)=14=15-1 - [e346. 區間和練習](https://zerojudge.tw/ShowProblem?problemid=e346) - [d206. 00108 - Maximum Sum](https://zerojudge.tw/ShowProblem?problemid=d206) + 『差分』為陣列相鄰兩項的差值($D_i = A_i-A_{i-1}$)。要多次在區間 $[l, r]$ 加上一個數值 $x$ 時，只需調整差分($𝐷_𝑙$+=$𝑥$，$𝐷_{r+1}$-=$𝑥$)，最後差分序列的前綴和即為原序列。 例如：A=[1, 5, 3, 6, 2, 4]，差分數列 D=[1, 4, -2, 3, -4, 2] A[1]~A[3]+10　A~1~=[1, 15, 13, 16, 2, 4]　　D~1~=[1, **14**, -2, 3, **-14**, 2] A[2]~A[4]+10　A~2~=[1, 15, 23, 26, 12, 4]　D~2~=[1, 14, **8**, 3, -14, **-8**] D~2~的前綴和＝[1, 15, 23, 26, 12, 4] 即為原序列。 - (差分計算) [e340. 差分練習](https://zerojudge.tw/ShowProblem?problemid=e340) - (區間加值) [q376. 取締違規 (Police)](https://zerojudge.tw/ShowProblem?problemid=q376) - [g597. 3. 生產線](https://zerojudge.tw/ShowProblem?problemid=g597) ### 4、進階資料結構 + 稀疏表(Sparse Table) - [BIT & Sparse Table](https://hackmd.io/@LittlePants/BJKNxEU6s) + 樹狀數組(BIT) - [BIT1](https://yuihuang.com/binary-indexed-tree/) - [BIT2](https://mtmatt.page/apcs/apcspracticaltest/my-apcs-handout/#more) + 線段樹 - [線段樹1](https://wiki.sam571128.codes/data-structure/segment-tree) - [線段樹2](https://yuihuang.com/segment-tree/) ## 一、遞迴 ### 1.1. 基本觀念與用法 + 遞迴在數學上是函數直接或間接以自己定義自己，在程式上則是函數直接或間接呼叫自 己。遞迴的思考方式與一般的不同，它不是直接的給予答案，而是間接的說明答案與答案的關係。(費式數列為例) + 遞迴函數一定會有終端條件(也稱邊界條件)。 + 遞迴程式好寫，但往往有效率不佳的問題，演算法裡面有些策略(如動態規劃)，可用來改善純遞迴的效率。 + 遞迴通常使用的時機有兩類： 1. 根據定義來實作。 2. 為了計算答案，以遞迴來進行窮舉暴搜。 ### 1.2. 實作遞迴定義 :::info [d001: 例題 P-1-1. 合成函數(1)](https://judge.tcirc.tw/problem/d001) + 合成函數的意思是它的傳入參數可能是個數字也可能是另外一個函數值。 + 以遞迴的觀念來思考，將一個合成函數的表示式定義為一個函式 eval()，函式從輸入讀取字串，並回傳函數值。 + 流程只有兩個主要步驟，第一步讀取一個字串(只有 f、g、數字)。第二步根據這個字串分 別進行 f 或 g 函數值的計算或是直接回傳字串代表的數字。 + 如何計算 f 與 g 的函數值？ 如果是 f，因為它有一個傳入參數，這個參數也是合成函數，所以遞迴呼叫 eval() 來取得此參數值，再根據定義計算。如果是 g 則呼叫 eval() 兩次取得兩個參數。 ::: :::warning [d002: 習題 Q-1-2. 合成函數(2) (APCS201902)](https://judge.tcirc.tw/problem/d002) ::: :::info [d003: 例題 P-1-3. 棍子中點切割](https://judge.tcirc.tw/problem/d003) + 設座標存於 p[]，遞迴函式的虛擬碼 ```c= long long cut(int left, int right) { 找出離中點最近的切割點 m; return p[right]-p[left] + cut(left,m) + cut(m,right); } ``` + 如何找到某一段的中點呢？離兩端等距的點座標為 x = (p[right] + p[left])/2。所以要找某個 m，滿足 p[m-1] < x <= p[m]，然後要找的切割點就是 m-1 或 m (看哪一點離中點較近，如相等就取 m-1)。本題因為數值的範圍不大，採取最簡單的線性搜尋即可(p.22 p_1_3a.cpp)。但因為座標是遞增的，可用二分搜會更快。(p.22 p_1_3b.cpp，p.23 p_1_3 c.cpp) ::: :::warning [d004: 習題 Q-1-4. 支點切割 (APCS201802) (@@)](https://judge.tcirc.tw/problem/d004) + [解題參考](https://www.youtube.com/watch?v=J_yAEwEg_Ak) + 找到最佳切點之後對左右兩塊遞迴求解。 + 各點數字與到切點距離的乘積的總和，可以看成計算槓桿的力矩，所以最佳切點是左右兩邊力矩和最相近的時候。 + 如何有效率的找最佳切點？對於一個切點計算力矩需要包含每一個點的數字與距離，並沒有可以節省的，但是每次移動切點都要重新計算就有用[前綴和(p.15)](https://drive.google.com/file/d/1DBjfn47BKtu6hInoaeX5-9ju_bTCfub9/view?usp=drive_link)加速。 ::: :::warning [d005: 習題 Q-1-5. 二維黑白影像編碼 (APCS201810)](https://judge.tcirc.tw/problem/d005) + [解題參考](https://yuihuang.com/zj-f637/) ::: ### 1.3. 以遞迴窮舉暴搜 :::info [d006: 例題 P-1-7. 子集合乘積](https://judge.tcirc.tw/problem/d006) + 要窮舉子集合可用迴圈窮舉(p.27)或遞迴。 + 遞迴副程式 rec(i, prod) 表示目前考慮第 i 個元素是否選取納入子集合，而 prod是目前已納入子集合元素的乘積。 ::: :::warning [d007: 習題 Q-1-8. 子集合的和 (APCS201810, subtask)](https://judge.tcirc.tw/problem/d007) ::: :::info [a065: 例題 P-1-9. N-Queen解的個數](https://judge.hwsh.tc.edu.tw/ShowProblem?problemid=a065) + [棋盤](https://www.datagenetics.com/blog/august42012/) + backtracking + 以一維陣列 col[] 記錄皇后的座標。陣列索引為皇后的row，值為皇后的col。 | ![](https://hackmd.io/_uploads/S1xlCWDQxl.png =180x) | q[1]={1,1}<br>q[2]={2,3}<br>q[3]={3,5}<br>$\vdots$<br>col[1]=1<br>col[2]=3<br>col[3]=5<br>$\vdots$| | -------- | :--------: | + 皇后衝突的判斷![EX_5_2：八皇后衝突判斷(ap325)](https://hackmd.io/_uploads/HyInkzDXxg.png =100x) + 如何加速？之前的方法是對每一個可能的位子，都從頭檢查是否會被攻擊，缺乏效率。可以換個角度，對之前的皇后，標記它在此列可以攻擊的位子，遇到這些位子就跳過不用檢查了。(p.30 p_1_9c.cpp) ::: :::warning [d008: 習題 Q-1-10. 最多得分的皇后](https://judge.tcirc.tw/problem/d008) ::: <br/> ## 二、排序與二分搜 + 排序與搜尋大多都會與其他的演算法結合，成為解題方法中的一個步驟，單獨考的並不多。 ### 2.1. 排序 + 競賽主要為排序的應用技巧而非排序演算法，排序通常有幾個運用的時機： - 需要把相同資料排在一起。 - 便於快速搜尋。 - 做為其他演算法的執行順序。例如 Sweeping-line, Greedy, DP。 + 自行練習 p.35-p.38 sort、比較函數、struct、pair + 補充練習 - [a362. 1. 搬雕像](https://zerojudge.tw/ShowProblem?problemid=g277) - [c230. 松鼠旅行](https://zerojudge.tw/ShowProblem?problemid=g277) - [g277. 3. 幸運數字](https://zerojudge.tw/ShowProblem?problemid=g277) :::info [d010: 例題 P-2-1. 不同的數—排序](https://judge.tcirc.tw/problem/d010) + 除了 vector、sort外，再練習以 set 實作。 ::: ### 2.2. 搜尋 + 基本二分搜的寫法 - 自行練習 p.40-p41 2種2分搜(左右搜、一路往前跳)的寫法 - 補充練習：(裸題) [d732. 二分搜尋法](https://zerojudge.tw/ShowProblem?problemid=d732) + C++的二分搜函數以及相關資料結構 - 自行練習 p.42-p.44 binary_search、lower-bound、upper_bound - 補充練習：[d186: 11461 - Square Numbers](https://zerojudge.tw/ShowProblem?problemid=d186) 以 vector、lower-bound、upper_bound 改寫。 - [常用C++ algorithm：lower_bound & upper_bound](https://yuihuang.com/cpp-algorithm-lower-bound-upper-bound/) :::info [d011: 例題 P-2-2. 離散化 – sort](https://judge.tcirc.tw/problem/d011) + 將原陣列a中的相異元素排序在b陣列中，對於原陣列a中的元素，置換成它在b陣列中的index。 + 在b陣列中找到a[i]可用二分搜加速。 + 離散化為把一個數列從數值改成大小排名，例如 88 7 9999 666 變成 2 1 4 3，離散化後只會保留數值之間的大小關係。其目的可將值域範圍很大(如$10^9$)，但出現的數值個數不多(如N=1000)的情況下，轉換成更小、連續的整數範圍，加快處理效率。 ::: :::warning [d024: 例題 P-2-15. 圓環出口 (APCS202007)](https://judge.tcirc.tw/problem/d024) + 每次要在一個正整數陣列中，對於某個開始位置，找到一個最小的區間，滿足區間和大於等於某輸入 Q(i)。 + 關於圓環結尾時，有兩個簡單的處理方式，一個是判斷超過結尾時，從頭開始。另外一種方式因為 q~i~ 不會超過 p 的總和，所以將原陣列複製一次，再求前綴和，可簡化操作；如果沒有此限制，也只需將 q~i~ 預先 mod p 的總和即可。 + 直接一個一個往下找，效率不好。有效率的搜尋自然想到二分搜，但是二分搜必須是在單調序列上才能使用，而且要找的是區間和，所以把所有房間的點數改成計算出前綴和(正數的前綴和必然是遞增的)，要找的區間和也自然的轉換成找一個前綴和。 + [解題參考](https://www.youtube.com/watch?v=KT23btgYQqA) ::: + 基本二分搜的寫法C++可供搜尋的容器(set/map) - 自行練習 p.46-p.50 set、multiset、map、multimap - P-2-2C 以 map 改寫 ### 2.3. 其他相關技巧介紹 #### 快速冪：如何快速計算 $x^y$ 的方法 :::info [d012: 例題 P-2-3. 快速冪](https://judge.tcirc.tw/problem/d012) + 方法一：若 $y=19$，二進制是 $10011$，則計算 $x^{19} = x^{16} * x^2 * x^1$。 + 方法二：以遞迴的寫法，若 $y$ 是偶數，則求出 $x^{\frac{y}{2}}$ 次方後自乘；若 $y$ 是奇數則先遞迴求出 $x^{y-1}$ 後再乘一次 $x$，終止條件為 $y=0$ 時，return 1。略慢於方法一，但競賽中數量級正確通常都不會TLE。(練習2種作法) + 模除的分配率 ${\displaystyle (a+b){\bmod {n}}=[(a{\bmod {n}})+(b{\bmod {n}})]{\bmod {n}}}$ ${\displaystyle ab{\bmod {n}}=[(a{\bmod {n}})(b{\bmod {n}})]{\bmod {n}}}$ ::: :::warning [d013: 習題 Q-2-4. 快速冪--200 位整數](https://judge.tcirc.tw/problem/d013) + x 超過long long，先求 x % p + 以 string 讀取 x，將每個字元轉成數值的過程，不斷%p。 例如 x=123=(1\*10+2)\*10+3，x%p=((((1\*10%p+2)%p)\*10)%p+3)%p ::: #### 快速計算費式數列 :::info [d014: 習題 Q-2-5. 快速計算費式數列第 n 項](https://judge.tcirc.tw/problem/d014) + $\begin{bmatrix} f[n] \\ f[n-1] \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} f[n-1] \\ f[n-2] \end{bmatrix} \ , \ \begin{bmatrix} f[1] \\ f[0] \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$ 將上式迭代展開，因為矩陣滿足結合律，所以可以得到 $\begin{bmatrix} f[n] \\ f[n-1] \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1} \times \begin{bmatrix} f[1] \\ f[0] \end{bmatrix} \ 或 \ \begin{bmatrix} f[n+1] \\ f[n] \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n} \times \begin{bmatrix} f[1] \\ f[0] \end{bmatrix}$ 或 + 可以用快速冪的方式算出矩陣 A 的 n 次方，$f[n]=A^n[1][0]$。 ::: #### 模逆元 + Modular multiplicative inverse 就是在模運算下的乘法反元素，稱為「[模反元素](https://zh.wikipedia.org/zh-tw/%E6%A8%A1%E5%8F%8D%E5%85%83%E7%B4%A0)」或「模逆元」。對於任何一個正整數 a，它的模 p 乘法反元素就是滿足 (a * b) % p = 1 的整數 b。 + 如何計算 a 的模逆元？ 窮舉法的效率太差。在許多運用場合 p 是一個質數，而且探討的整數範圍都只在 0 ~ p-1。在這些假設下，利用「費馬小定理」即可快速計算模逆元：「若 p 為質數，對任意正整數 a，a^p-2^ % p 是 a 在[1, p-1]區間的唯一乘法反元素。」根據此性質搭配快速冪就可以在 O( log( p ) ) 計算出模逆元。 :::info [d017: 習題 Q-2-8. 模逆元 (*)](https://judge.tcirc.tw/problem/d017) + [費馬小定理](https://www.youtube.com/watch?v=SyK3IXPITco) a^p-1^ ≡ 1 (mod p) ➡︎ a^p^ ≡ a (mod p) a^p-2^ * a^2^ ≡ a^-1^ * a^2^ (mod p) a^p-2^ 和 a 的模逆元 a^-1^ 在 mod p的情況下是相等的。 + [數學上的模逆元](https://meteor.today/article/5hal9d)、[程式設計上的模逆元](https://meteor.today/article/TKXPid) ::: ### 2.4. 其他例題與習題 :::info [d015: 例題 P-2-6. Two-Number problem](https://judge.tcirc.tw/problem/d015) + 方法一：將 A 排序後，對 B 中的每一個 b，以二分搜在 A 中尋找 K-b。 + 方法二：將 A 與 B 分別排序後，對 A 中的每一個 a，在 B 中以滑動的方式找 K-a。 + 方法三：把 A 放進 set，對每個 B 中的每一個 b，在 set 中找 K-b。 ::: :::warning [d016: 習題 Q-2-7. 互補團隊 (APCS201906)](https://judge.tcirc.tw/problem/d016) + 以一個整數表示一個集合，第i個bit設為1代表第i個字母在集合中。兩個互補團隊的數字 xor 後會等於 2^m^ -1。 + 若 a xor b = c 則 a xor c = b + STL map ::: #### 折半枚舉 :::info [d018: 例題 P-2-9. 子集合乘積(折半枚舉) (@@)](https://judge.tcirc.tw/problem/d018) + 可以透過枚舉所有的子集合來測試哪些的組合乘積為 1。在第一章以遞迴來枚舉所有子集的方法，效率是 O(2^n^)，本題 n 可能達到 36，顯然無法在一秒內完成。 + 逐一考慮每一個元素，以一個 map M1 來記錄著目前所有可能的子集合乘積，相同的乘積只記錄一筆，但記錄能產生此乘積的子集合個數。對於下一個元素 a[i]，把原有的所有可能再乘上，就是新的可能乘積。在計算過程，新的乘積不能直接加到原來的裡面，否則無法分辨新舊。因此要利用一個 map M2 來暫存，當一個元素處理完畢後交換 M1 與 M2，以便下一個元素時再從 M1 計算到 M2。這個修改的方法，在相同的乘積多的場合效率會有所改善，但還是不足以通過所有測資(80%)。 + 在這種場合可以使用折半枚舉來做的更有效率一點。 - 對於 n 個數字，我們先將他任意均分為兩半 A 與 B，我們要找的解(子集合乘積等於1)有三種可能：在 A 中、在 B 中、以及跨 A, B 兩端(包含兩邊的元素)。 - 對 A 與 B 分別去窮舉它們的子集合乘積，可以找到在 A 中與在 B 中的解。 - 對於跨兩邊的解，將其中一邊(例如 B )的所有子集合乘積收集在某個容器中後，對每一個 A 的子集合乘積 x ，在 B 的子集合乘積中去搜尋 x 的模逆元 y 的個數(使得 xy = 1 的 y)。 - 在 A 與 B 中都可能有很多相同元素，要把 B 的子集合乘積中，相同的乘積予以合併。至於 A 那一邊，合併也可以提升效率，但 worst case 複雜度沒有影響。 - 時間複雜度：對 $n/2$ 個元素窮舉子集合需要 $O(2^{n/2})$，兩邊都做所以乘以 2，排序需要 $O(n\times 2^{n/2})$，接著對 $2^{n/2}$ 個數字在 $2^{n/2}$ 個數字中做二分搜，需要的時間是 $O(2^{n/2}\times log_2(2^{n/2}))= O(2^{n/2} * (n/2))=O(n\times 2^{n/2})$，所以總時間複雜度是 $O(n\times 2^{n/2})$，比起單純窮舉 $O(2^n)$ 要快得多了。 - 利用折半枚舉將問題規模從 $2^n$ 降至 $2^{𝑛/2}$。 ::: :::warning [d019: 例題 Q-2-10. 子集合的和 (折半枚舉)](https://judge.tcirc.tw/problem/d019) + 習題 Q-1-8. 子集合的和，當時的 n<26，本題把他放寬到 38。 ::: #### 尋找最接近區間和 :::info [d020: 例題 P-2-11. 最接近的區間和 (*)](https://judge.tcirc.tw/problem/d020) + 只用前綴和，O(n^2^) 會 TLE。 + 一個區段用兩端點[l,r]表示，對於可能的右端 r，要設法找到讓 A[l:r]的和最接近 K 而不超過 K 的左端 l，然後對所有的 r 再找出最佳解。所以問題的核心為如何對任一右端計算出最好的解。 + 令 psum[i] 表示前 i 項的和，對任一右端 r，sum(A[i:r]) = psum[r]-psum[i-1]，因此要使 sum(A[i:r]) 不超過 K 又最接近 K，就是要找 psum[i-1] >= psum[r]-K 的最小值。 + 因此讓 r 從小往大跑，以 set 維護好所有 i<r 的 psum[i]，然後找到 psum[r]-K 的 lower_bound()。時間複雜度是O(nlog(n))，因為在 set 中搜尋是 O(log(n))。 ::: :::warning [d021: 習題 Q-2-12. 最接近的子矩陣和 (108 高中全國賽) (*)](https://judge.tcirc.tw/problem/d021) + 只用前綴和會 TLE。 + 利用 set 儲存已經計算好的矩形區塊和。 auto it = st.lower_bound(sum-k); ::: <br/> ## 三、佇列與堆疊 ### 3.1. 基本原理與實作 + 自行練習 p.74-p.75 STL stack、queue、deque + 堆疊補充練習 - [i213. stack 練習](https://zerojudge.tw/ShowProblem?problemid=i213) - [b838. 104北二2.括號問題](https://zerojudge.tw/ShowProblem?problemid=b838) + 佇列補充練習 - [e447. queue 練習](https://zerojudge.tw/ShowProblem?problemid=e447) ### 3.2. 應用例題與習題 + 佇列、堆疊與雙向佇列常常是其他演算法裡面的一個基本步驟，單獨出現不多。 #### 堆疊 :::info [d026: 例題 P-3-2. 括弧配對](https://judge.tcirc.tw/problem/d026) + 如果是左括弧的一種，就將其壓入堆疊。如果是右括弧，取出堆疊最上方的左括弧與其配對，如果不配對，則錯誤。字串結束後堆疊中還有東西，也是錯誤。 + 實作時要避免很繁瑣的窮舉三種括弧，可以使用一個小技巧，將 6 種括弧字元對應到整數 0~5，先排左括弧再排右括弧，同類的一對的讓他們剛好差 3，這樣可以簡單的檢查是否配對。 + 空的 stack 執行 sk.top() 會錯誤。 ::: :::warning [d027: 習題 Q-3-3. 加減乘除](https://judge.tcirc.tw/problem/d027) + 以堆疊 1 記錄運算元(數字)，堆疊 2 記錄運算子(+\-*/)。 - 遇到運算元就放入堆疊 1。 - 遇到運算子則和堆疊 2 上端的運算子比較優先權，如果比較小，則堆疊 2 內的運算子先運算。 + [中序式轉後序式](https://openhome.cc/zh-tw/algorithm/computation/postfix/) ::: :::info [d028: 例題 P-3-4. 最接近的高人 (APCS201902, subtask)](https://judge.tcirc.tw/problem/d028) + 可以假設在最前方位置 0 的地方有個無限大的數字，這樣可以簡化減少邊界的檢查。 + 最直觀的做法為對每一個 i，從 i-1 開始往前直到碰到比他大的數字，但是最壞的情形下，每個人都要看過前方的所有人，時間複雜度是 O(n^2^)。因為 n 是 2e5，一定要用 O(n) 或 O(nlog(n))的方法。 + 要如何改善複雜度？想想是否有沒有用的計算或資料。如果 a[i-1] <= a[i]，那麼 a[i-1] 不可能是 i 之後的人的高人(因為由後往前找的時候，會先碰到 a[i])。同理任何 j<i 且 a[j] <= a[i]的 a[j] 都是沒有用的。如果丟掉沒用的，會剩下一個遞減的序列。只要維護好這個遞減序列，就可以提高計算效率。 + 單調序列要用二分搜嗎？其實連二分搜都不需要。為什麼？當處理到 a[i] 時，要先把單調序列後方不大於 a[i] 的成員全部去除，然後最後一個就是 a[i] 要找的高人。因為既然要做去除的動作，就一個一個比較就好了。 + 要如何維護這個單調序列呢？第一個想法可能是將那些沒用的刪除，但陣列禁不起的折騰就是插入與刪除，因為必須搬動其後的所有資料。想想要做的動作是：每次從序列後方刪除一些東西，再加入一個東西，所以堆疊最適合。 + 均攤分析(amortized analysis) 經典題。 時間複雜度？看到雙迴圈會以為是 O(n^2^)，雖然程式有雙迴圈，內層 while 迴圈也的確有可能某幾次會跑到 O(n)，但是整體的複雜度其實只有 O(n)。原因是雖然單一次 while 迴圈可能跑很多個 pop，但是全體算起來 pop 不會超過 n 次，因為每個身高只會進入堆疊一次，進去一次不可能出來兩次，所以整體的複雜度是O(n)。這種算總帳的方式來計算複雜度稱為均攤分析(amortized analysis)。 + 前面的做法是由前往後掃，做到 i 的時候往前找 i 的高人。練習由後往前，做到 i 時看看 i 是誰的高人 p.86。 ::: :::warning [d029: 習題 Q-3-5. 帶著板凳排雞排的高人 (APCS201902)](https://judge.tcirc.tw/problem/d029) + 最左邊界的無限大高度，初值要超過 2*10^7^。 + [解題參考](https://www.youtube.com/watch?v=nd0cncEfw38) ::: #### 佇列 + [C++ queue 和 deque的区别](https://blog.csdn.net/qq_25800311/article/details/89060069) :::info [d030: 例題 P-3-6. 砍樹 (APCS202001)](https://judge.tcirc.tw/problem/d030) + 在兩個邊界種上無限高的樹，這是常用的技巧，可以省卻檢查邊界條件的麻煩。 + 思考目前不能被砍除的樹，什麼狀況會變成可以砍除呢？一定是與他相鄰的(還存活的)樹被砍掉，才有可能空出多餘的空間。所以以一個佇列 Q 存放那些砍除的樹，一開始先檢查一次那些樹可以被砍除，把他們放入 Q。然後將 Q 中的樹拿出來，檢查他左右相鄰的樹是否可以變成可以砍除，如果可以，就砍除並放入 Q，這樣做直到 Q 中沒有樹為止。 + 以串列鏈結的觀念，記錄某棵樹的左右鄰居。 + 自行練習 p.93-p.94 堆疊的做法。 ::: #### 滑動視窗(Sliding window) + 滑動視窗基本是以兩個指標維護一段區間，然後逐步將這區間從前往後(從左往右)移動。維護兩個指標這一類的方法也有人稱為雙指標法。 + 爬行法本質上是「滑動視窗」的一種變化版本，兩個指標一前一後像毛毛蟲爬行，維持某種區間條件（例如總和 ≤ 某值）。 + 補充練習 - [b542. 聽到這兩個人的身高，讓十萬人都驚呆了](https://zerojudge.tw/ShowProblem?problemid=b542) - [d194. 11572 - Unique Snowflakes](https://zerojudge.tw/ShowProblem?problemid=d194) :::info [d031: 例題 P-3-7. 正整數序列之最接近的區間和](https://judge.tcirc.tw/problem/d031) + 與 P-2-11 幾乎相同，但本題限制輸入的數字為正整數，比較簡單。P-2-11正負不限，須以 set 來解。 + 一開始先固定左端在 0 的位置，從 0 開始一直移動右端尋找區段的和不超過 K 的最大。因為數字都是正的，右端越往右移，區段和就越大，當移動到不能再移時(否則就會超過 K),我們就找到了「以 0 為左端的最好區間」。 + 接著將這個區段(視窗)逐步右移，每次先將右端往右移動一格，這時總和可能會超過 K，所以要移動左端直到滿足區段和不超過 K 為止。每次右端移動一格，就會找到以此為右端的最佳解，當視窗向右滑到底時，就找出了最佳解。 ::: :::info [d032: 例題 P-3-8. 固定長度區間的最大區段差](https://judge.tcirc.tw/problem/d032) + 連續 L 個格子是一個窗戶，長度 N 的序列有 N-L+1 個可能的窗戶位置，對每一個位置，把窗戶內的最大值減去最小值得到區段差。所有 N-L+1 個區段差中要找到最大的，無腦直接每個區段跑一遍找最大最小需要 O(L)，N-L+1 個區段就是 O(L(N-L+1))，L=N/2 時，就是 O(N^2^)。 + 解法主要要紀錄區段內的最大值與最小值，當區段往右移動，更新最大與最小值。乍看之下，更新最大、最小值很容易，因為只移進來一個值，移出去一個值。可是如果移出去的是最大值，那最大值會變成多少呢？可能會變也可能不變，問題似乎沒有那麼簡單。 + 要不斷的找出窗戶內的最大值與最小值，先看最大值的找法(最小值的做法一樣)。其實這一題跟「P-3-4 最接近的高人」類似，有個相同的單調性觀察：「當窗戶的右端推到 i 時，在 i 之前所有不大於 seq[i] 的元素，對未來找最大值都是沒有用的。」因此可以刪除那些沒用的資料，只要維護好窗戶內的遞減子序列，與 P-3-4 不同處在於，因為窗戶會往右移動，資料有可能從窗戶左端離開，因此不能用堆疊來做，要用 deque 來做，時間複雜度 O(N)。 + set 可以簡單的找到最大與最小，移進移出也很方便，自行練習使用 multiset 的作法，時間複雜度 O(Nlog(N))。 ::: :::warning [d037: 習題Q-3-13. X差值範圍內的最大Y差值](https://judge.tcirc.tw/problem/d037) + 先對 x 座標排序。 + 宣告 deque<int> max_q,min_q; max_q 記錄 L 區間 y 最大值的索引，min_q 記錄 L 區間 y 最小值的索引。 + 當元素要從窗戶右端放入max_q時，先從前端移除超過L的點(離開窗戶)，再從後端移除所有小於它的點(這些點對找最大值沒用，max_q為遞減序列)，然後push_back至max_q內。 + min_q同理從後端移除所有大於它的點。 + 以迴圈讓窗戶的右端逐步往右推，處理完畢後 max_q.front()為窗戶內的最大值的點，min_q.front()為最小值的點。 ::: :::info [d033: 例題 P-3-9. 最多色彩帶](https://judge.tcirc.tw/problem/d033) + 把固定長度 L 的視窗，從左到右滑動過去，找出視窗內的顏色總數。 + 如何記錄視窗內的顏色數？因為顏色總數不大，可以準備一個陣列，cnt[i] 紀錄顏色 i 的出現次數。每次進入一個顏色，就將該顏色計數器加一，移出一個顏色就將顏色計數器減一。 + 如何計算視窗內的顏色數？每次都掃描陣列太浪費時間，只關注顏色數的變動即可。可以用一個變數記錄目前的顏色數，若 cnt[i]++ 之後變成 1，那就知道顏色數多了一種。如果 cnt[i]減 1 之後變成 0 就是少了一色，其他狀況的顏色數量沒變化。 ::: :::info [d034: 例題 P-3-10. 全彩彩帶 (需離散化或字典) (@@)](https://judge.tcirc.tw/problem/d034) + 維持一個視窗裡面包含所有的色彩，每次當視窗往右移一格時，檢查左端是否可以往右移以便縮減寬度 ，當視窗移到底之後，就已經檢查過所有可能的右端點，過程中找到最窄的視窗寬度就是答案。 + 何時左端可以縮減？如果左端點顏色在視窗內出現超過一次，就可以丟棄，否則左端不能右移。 + 顏色編號可能達到 10 億，不可能開一個 10 億的陣列，但是資料最多只有 20 萬個，顏色當然最多也只有 20 萬種，可用離散化觀念處理。map<int, int>記錄該顏色的數量(key表顏色，value表數量)。因為順序不重要，可用unordered_map查詢會更快。 ::: :::warning [d035: 習題 Q-3-11. 最長的相異色彩帶](https://judge.tcirc.tw/problem/d035) + 以 queue 儲存最長相異色彩帶，往右的顏色如果重複，將 queue 中此顏色之前的顏色刪除。 ::: :::warning [d036: 習題 Q-3-12. 完美彩帶 (APCS201906)](https://judge.tcirc.tw/problem/d036) + 滑動視窗，使用 queue，模擬區間由左向右滑，左邊出去一個顏色(front pop)，右邊進來一個顏色(back push)。比對 queue 內相異顏色數量是不是等於 M。 ::: <br/> ## 四、貪心演算法與掃瞄線演算法 ### 4.1. 基本原理 + 假設一個問題可以藉由一系列的選擇來解決，貪心演算法為在每一步的選擇中，都採取在當前狀態下的最佳選擇，從而希望導致結果是最佳解的演算法。 + [使用貪心策略的演算法](https://blog.csdn.net/weixin_46072771/article/details/106365035) - 活動選擇(Activity Selection Problem) - 物品可分割背包問題(Fractional Knapsack Problem) - 霍夫曼編碼（Huffman Coding） - 最小生成樹(Min spanning tree problem) : Kruskal’s algorithm and Prim’s algorithm - Dijkstra 最短路徑演算法 :::info [d042: 例題 P-4-1. 少林寺的代幣](https://judge.tcirc.tw/problem/d042) + 當代幣之間不一定是倍數關係時(如 1、3、4)，局部最佳解不一定會組成全局最佳解。 ::: ### 4.2. 例題與習題 #### 4.2.1. 單欄位資料排序 :::info [d043: 例題 P-4-2. 笑傲江湖之三戰](https://judge.tcirc.tw/problem/d043) + 依 Greedy 的想法用猜的，每次都派我方最強對戰敵方最強？範例測資好像對，反例？ + 假設我方目前最弱的戰力是 a ，對方最弱的是 b，如果 a <= b，則 a 對誰都不會贏，可以忽略。否則 a > b，我們宣稱「一定有一個最佳解是派 a 去戰 b」。證明如下： + 假設在一個最佳解中，a 對戰 y，x 對戰 b，此時可以將其交換為「a 對 b 且 x 對 y」。 因為原本 x 對 b 會贏，交換後 a 還是可以贏 b ( 因為根據假設 a > b)。而 x 因為大於 a，所以 x 對 y 不會比原本 a 對 y 差，所以交換後勝場數不會變少。 既然如此，我們可以確定派 a 對戰 b 一定可以得到最佳解。將 a 與 b 移除後，繼續依照上述原則挑選。 我：a x 敵：b y + STL sort ::: :::info [d044: 例題 P-4-3. 十年磨一劍(最少完成時間)](https://judge.tcirc.tw/problem/d044) + minimum completion time 經典題 + 假設 job[i] 的順序是最佳解，若存在 job[i]>job[i+1]，那麼交換這兩個相鄰工作，其它的工作時間不會改變，但這兩個工作的完成時間總和會**減少**，因此最佳解中不可能長的排在短的前面。 + 這種考慮相鄰交換的情形是一個證明的技巧（交換論證法），因為其它的工作不會改變，可以得到很簡單的證明。 ::: #### 4.2.2. 結構資料排序 :::info [d045: 例題 P-4-4. 幾場華山論劍(activity selection)](https://judge.tcirc.tw/problem/d045) + activity selection problem 經典題。數線上有若干線段，要挑選出最多的不重疊的線段。依 Greedy 的想法用猜的，盡量挑短的，範例就錯了。 + 若[x, y]是所有現存線段中右端點最小的，那麼一定有個最佳解是挑選了 [x, y]。證明如下： 假設最佳解沒有挑 [x, y]，令 [a, b] 是最佳解中右端點最小的。 根據假設 y 會<= b，因此將 [x, y] 取代 [a, b] 不會重疊到任何最佳解中的其他線段，可以得到另外一個最佳解包含[x, y]。 　　a--------b x--------y + 根據上述性質，不斷地將最小右端的線段挑選進解答，然後略過與它重疊的線段。 + 如果需要使用 struct 來存資料，需自訂比較函數。亦可用 STL 的 pair（依欄位順序比較）([C++ 17 結構化綁定](https://zh-blog.logan.tw/2019/10/29/cxx-17-structured-binding/))。 ::: :::info [d046: 例題 P-4-5. 嵩山磨劍坊的問題(加權最小完成時間)](https://judge.tcirc.tw/problem/d046) + 如果 w 一樣，就跟 P-4-3 一樣。有權重，時間短的不一定在前面。 + 如果只看時間，時間短的排前面；如果只看權重，權重大的應該排前面，因為延遲的話罰得重。但是兩者都要考慮的話，t/w 值小的排在前面。證明如下： + 假設磨 a, b 之前劍所需的時間為 x，則之前的順序，不會影響 (a,b) 或 (b,a) 的扣款總額的計算，所以只要考慮 a, b 順序即可。 - (a,b) → [x+t(a)]*w(a) + [x+t(a)+t(b)]*w(b) = x(w(a)+w(b)) + t(a)*w(a) + t(b)*w(b) + **t(a)\*w(b)** - (b,a) → [x+t(b)]*w(b) + [x+t(a)+t(b)]*w(a) = x(w(a)+w(b)) + t(a)*w(a) + t(b)*w(b) + **t(b)\*w(a)** - 我們希望找到成本較低的順序，如果原順序 (a, b) 較優，則必須滿足 t(a)\*w(b) < t(b)\*w(a) ⇨ t(a)/w(a) < t(b)/w(b)。所以如果劍 a 的「時間/權重」比率小於劍 b，那麼將劍 a 放在劍 b 之前會得到更優的結果。 - 實作直接使用浮點數 t / w 來比較可能會因為精度問題而出錯，所以排序比較函式改為 a.t * b.w < b.t * a.w ，這個整數運算式來進行排序，來避免浮點數的誤差。 ::: :::warning [d047: 習題 Q-4-6. 少林寺的自動寄物櫃(APCS201710)](https://judge.tcirc.tw/problem/d047) + 假設a,b其上物品的重量為x，則這些物品的順序，不會影響(a,b)或(b,a)消耗的能量的計算，所以只要考慮a,b順序即可。 - (a,b)-> x*f(a) + (x+w(a))*f(b) = x(f(a)+f(b)) + w(a)*f(b) - (b,a)-> x*f(b) + (x+w(b))*f(a) = x(f(a)+f(b)) + w(b)*f(a) - 排序比較函式 a.w * b.f < b.w * a.f ::: #### 4.2.3. 以PQ處理動態資料(*) - priority queue 補充練習：[d221. 10954 - Add All](https://zerojudge.tw/ShowProblem?problemid=d221) :::info [d048: 例題 P-4-7. 岳不群的併派問題(Two-way merge) (*)](https://judge.tcirc.tw/problem/d048) + Two-way merge tree，[Huffman code](https://zh.wikipedia.org/zh-tw/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81) + 要每次找出最小的兩個數，將他們刪除，再將他們的和放入。 + priority_queue 預設是最大值在top(大->小)，如果要小->大，可以簡單將數值加個負號；或 priority_queue< LL, deque<LL>, greater<LL> > pq; ::: :::warning [d053: 習題 Q-4-8. 先到先服務 (*)](https://judge.tcirc.tw/problem/d053) + 每一客人到最早可以被服務的櫃檯。依輸入序，將其時間與優先佇列中最小值相加後，再放入優先佇列。 ::: #### 4.2.4. 外掛二分搜 + 補充練習：對答案二分搜 → 答案必須具「單調性」才能使用。 - [f815. TOI_y21m4_a01遊戲升等](https://zerojudge.tw/ShowProblem?problemid=f815) - [c575. APCS 2017-0304-4基地台](https://zerojudge.tw/ShowProblem?problemid=c575) - [h084. 4. 牆上海報](https://zerojudge.tw/ShowProblem?problemid=h084) :::info [d049: 例題 P-4-9. 基地台 (APCS201703)](https://judge.tcirc.tw/problem/d049) + 服務點可以看成數線上的點，基地台涵蓋範圍可以看成數線上的線段，亦即計算以 K 根長度相同的線段蓋住所有的點，最小的線段長度 R。 + 如果題目改為給數線上 N 個點以及 R，最少要用幾根(K)長度 R 的線段才能蓋住所有輸入點，如何以Greedy思考？ - 考慮座標值最小的點 P，如果有一個解的最左端點小於 P，可以將此線段右移到左端點對齊 P，這樣的移動不會影響解的合法性，因此可以得到結論：「一定有一個最少 K 的最佳解，是將一根線段的左端放在最小座標點上。」 - 因此可以放上一個線段在[P, P+R]，並略過所有被蓋住的點。對剩下的點繼續此步驟，直到所有的點被蓋住，就可以找到最小的 K 值。 + 回到原來的問題，假設 $f(R)$ 可以以上述演算法，求得給定長度 R 時的最少線段數。很直覺地，當 R 增加時，$f(R)$ 必然只會**相同或減少**(滿足二分搜的單調性要求)，因為用更長的線段去蓋相同的點，不會需要更多線段。所以就可以用二分搜來找出最小的 R，滿足 $f(R) <= K$。 ::: :::warning [d054: Q-4-10. 恢復能量的白雲熊膽丸](https://judge.tcirc.tw/problem/d054) + 每次檢測的能量可能 < p[i]。 ::: #### 4.2.5. 掃描線演算法sweep-line + 想像用一條掃描線沿著某個方向掃描，過程中記錄某些資料或維護某些結構。與貪心演算法類似，往往第一步就是排序。常見的題目有數線上的點或線段，以及平面上的點或直線。 :::info [d050: 例題 P-4-11. 線段聯集 (APCS 201603)](https://judge.tcirc.tw/problem/d050) + 開10^8^bool陣列，讀一筆線段就從L標記到R，最後計算標記的數量。時間O(n)*O(10^8^)可行嗎？ 空間？ + 基本想法是將線段逐一加入目前的聯集 S (S 顯然是一群不相連的線段)。每次加入一條線段時，如果它與 S 中的線段沒有交集，那就太好了，直接把它放進去就行了；如果有交集呢？就必須將有交集的部分找出來做成聯集，這樣做非常的麻煩。 + 試試看掃描線的想法，先將輸入線段依**左端點**座標排序，想像掃描線從左往右掃，過程中一樣保持住目前已經看到的線段的聯集 S。掃描過程可能碰某個線段的左端或是右端(其他的位置對線段聯集的變化並無影響可以忽略)。 + 當碰到某線段[x,y]**左端**時，代表有一個線段要加入 S，[x,y]最多只會跟 S 中的一條線段(**最後一條**)有交集。 - 如果[x,y]左端點 > S 中最後一條線段的右端點，表示前一線段已結束，計算並加總覆蓋長度。(不重疊) - 如果[x,y]左端點 <= S 中最後一條線段的右端點，表示最後一條線段可延續，延長最後一條線段右端點位置即可。(重疊) ::: :::warning [d051: 例題 P-4-12. 一次買賣](https://judge.tcirc.tw/problem/d051) + 範例中已暗示挑選最大值與最小值並非正確的答案。 + 只需要考慮在第 i 天賣出的最大獲利，然後對各個 i 取最大值就是答案了。 + 第 i 天賣出的最大獲利當然就是買在 i 以前出現的最小值，也就是 i-1 的 prefix-minimum。所以可以一路掃描過去，維護好 prefix-min，並且每次讀入資料時都更新最小值及最大獲利即可。 ::: :::warning [d052: 例題 P-4-13. 最大連續子陣列](https://judge.tcirc.tw/problem/d052)(Maximum Subarray) + 最簡單窮舉 O(n^2^) 個所有區間，每一個區間再用一個迴圈求和，時間複雜度 O(n^3^)。 + 時間複雜度 O(n^2^) 有兩個方法，但還是會TLE。 - 一是對所有左端 i，用一個迴圈求出所有 [i,j] 區間的最大和。很容易做到，因為 sum(A[i:j+1]) = sum(A[i:j])+A[j+1]。 - 另一是利用前綴和(prefix sum)，先算好前綴和後，每一區間和可以用一個減法完成。 + 令 f(i) 是以 i 為右端(各種可能的左端)的最大區間和。觀察 f(i+1)與 f(i)的關係，f(i+1) 所選的左端如果在 i 之前，那麼一定與 f(i) 的左端一樣。所以 f(i+1) 只有以下兩種可能(兩者挑大的就好了)： - f(i+1)=f(i)+A[i+1]，左端與 f(i)相同。 - f(i+1)=A[i+1]，前面累積的小於0，左端在 i+1 (負對後面沒有幫助，所以就重新計算)。 + [Kadane 演算法 O(n)](https://www.youtube.com/watch?v=g-XcfPbLwQ8)：就像一代一代累積財產，若 f(i)>0，爸媽留給你的是正資產，則繼承過來；否則就拋棄繼承。 ::: :::info [d055: 例題 P-4-14. 控制點(2D-max)](https://judge.tcirc.tw/problem/d055) + 2D Maximal point，沒有其它點的 (x,y) 皆大於等於此點。 + 直接兩兩點比較，時間複雜度 O(n^2^)。 + 從左往右掃描，維護好目前找到的解(maximal points)，假設做到第 i-1 點時的解是 S(i-1)，考慮掃描到第 i 點 (x[i],y[i]) 時的狀況。S(i-1)中 Y 值**不大於** y[i] 的點都應該從解中移除。因為前面點的 X 值都不大於 x[i]，所以 (x[i],y[i]) 要加入 S(i)。 + 要如何刪除 S(i-1)中 Y 值不大於 y[i] 的點呢？因為 maximal 的點是以 X 值遞增的方式加入，他們的 Y 值一定是遞減，只要從後往前刪除就可以了。從後往前刪除，然後自己加入到最後面，所以 stack 是好的選擇。 + 從左往右掃描，前面找到的 maximal point 可能需要刪除。如果從右往左掃描，因為看到的點的 X 值是遞減，先找到的 maximal point 就一定是解！只要記住目前右方的最大 Y 值，下一點如果有更大的 Y 值，就可加入解中。 ::: :::warning [d056: 例題 P-4-15. 最靠近的一對(closest pair) (@@))](https://judge.tcirc.tw/problem/d056) + 想像一根垂直掃描線由左往右掃過去，每次碰到一個新的點，就找出新點與前面點的最近距離，並更新最小距離。若每個新進點都要跟前面的點計算距離，那這個方法跟窮舉沒兩樣，如何減少計算的數量？ + 假設目前碰到的點是 p[i]=(x[i], y[i])，而目前已求出來的最小距離是 d，令 S 是 p[0]~p[i-1]這些點的集合。 + 首先 S 中只有 Y 座標值在[y[i]-d, y[i]+d]範圍內的點才需要計算，因為其他的點到 p[i] 的距離必然大於 d。此外同樣的理由，S 中 X 座標值小於 x[i]-d 的點都不需要計算，而且不止這回合，以後碰到新點時，這些太左邊的點也都不需要計算了(因為越後面的點 X 座標越大)。 + 為了有效地找到 Y 座標在[y[i]-d, y[i]+d]範圍內的點，需要一個動態資料結構(multimap)，因為需要增加與刪除資料。 ::: ### 4.3. 其他習題 :::warning [d057: 習題 Q-4-16. 賺錢與罰款](https://judge.tcirc.tw/problem/d057) + Q-4-8 變化題 + 依工作所需時排序，若相同再依完工時間排序。 ::: :::warning [d058: 習題 Q-4-17. 死線高手](https://judge.tcirc.tw/problem/d058) + 依死線排序。 ::: :::warning [d059: 習題 Q-4-18. 少林寺的櫃姐 (@@)(*)](https://judge.tcirc.tw/problem/d059) + 二分搜櫃台數量，檢查是否可以在時間 D 內完成，看最少可以用幾個櫃台。(類似 P-4-9. 基地台) + 檢查方法為假設開 c 個櫃台，使用 priority_queue，取佇列中最小值相加後再放入佇列，計算完成時間。 ::: :::warning [d060: 習題 Q-4-19. 五嶽盟主的會議場所](https://judge.tcirc.tw/problem/d060) + 先依開始時間排序。 + 以 priority_queue 記錄處理過的時段，在 pq 內優先權的定義為結束時間大->小，移除此時間開始前的時段人數。 ::: :::warning [d061: 習題 Q-4-20. 監看華山練功場](https://judge.tcirc.tw/problem/d061) + 依開始練功時間排序。 + 在 x,y 間，若弟子段練功時間無法涵蓋(中間有空隙)，則無解。 ::: <br/> ## 五、分治演算法 + 分治是一種非常重要的演算法思維模式與策略，有很多重要的演算法都是根據分治的思維模式，例如快速排序法、合併排序法、快速傅立葉轉換(FFT)、矩陣乘法、整數乘法以及在一些在計算幾何的知名演算法都是分治的策略。 + 但相較於它的重要性，分治出現在題目中的比例卻不是那麼高，主要原因為 1.很多分治算法的問題都有別的解法的版本，樹狀圖的分治也往往歸類到動態規劃。 2.一些重要的分治算法已經被納入在庫存函數中，例如排序，還有一些則因為太難而不適合出題。 + 即使如此，分治還是很重要必須學習的思維模式，當我們碰到一個不曾見過的問題，分治往往是第一個思考的重點，因為分治的架構讓我們很容易找到比暴力或天真做法要好的方法。 ### 5.1. 基本原理 + 三個主要步驟 分割(divid)：將原本的問題分割成多個子問題(規模較小的同類問題)。 克服(conquer)：當子問題劃分得足夠小時，用相同的演算法遞迴地解決所有的子問題。 合併(combine)：合併(merge)所有子問題的解答成為原本問題的解答。(不一定所有的問題都需要，快速排序 vs. 合併排序) + 典型的分治算法: 演算法 f(S): 　　如果 S 已經很小，達到遞迴終端條件，則直接計算後回傳 f(S)，結束; 　　將 S 切割成 S1 與 S2; 　　遞迴呼叫計算 f(S1)與 f(S2); 　　將 f(S1)與 f(S2)合併成 f(S)後回傳; 結束; :::info [d052: 例題 P-5-2. 最大連續子陣列(分治)(同 P-4-13)](https://judge.tcirc.tw/problem/d052) + P-4-13 分別討論了 O(n^３^)、O(n^２^)、O(n) 的算法。假設不知道 O(n) 的解法，如何以分治的思維來尋找突破 O(n^2^) 的方法。 + 要計算陣列在[L,R-1]區間的最大連續和，首先將區間平均切成兩段 [L, M-1] 與 [M,R-1]，M=(L+R)/2。要找的解(子陣列)可能在左邊、右邊、或者跨過兩邊，所以只要三者取最大就是最後的答案。 + 左右可以分別遞迴求解，如何找出跨過兩邊的最大和？對於左邊，就笨笨的從中點往左一直累加，計算每一個可能左端的區間和，然後取最大；右邊同樣。然後兩者相加就是跨過中點的最大區間和。 + 事實上除了分治的概念外，找前綴和與後綴和的做法跟原來的 O(n^2^) 做法類似，只是原來的做法外面套了一個迴圈(嘗試所有左端)，這裡則是外面套了一個分治的遞迴。 + 直覺看起來複雜度沒什麼改善，讓我們來算一下：若 T(n) 是此算法在資料量為 n 時的複雜度，因為分割與合併的處理時間是 O(n)，所以 T(n)=2T(n/2)+O(n)，所以時間複雜度是 O(nlog(n))。分治用的好，天真的合併做法也可以得到不錯的解。仔細思考其中的原因，就會發現雖然每一次合併都是笨笨的做，但是參與合併的次數只有 log(n) 次，所以總次數為 nlog(n)。 ::: ### 5.2. 例題與習題 + 補充練習 - [f315. 4. 低地距離](https://zerojudge.tw/ShowProblem?problemid=f315) [(題解)](https://www.youtube.com/watch?v=IkZADcf3lcE&list=PLpmg1QLbgMuRQXHRkX9iDHyAVIW1D6OJF&index=23) :::info 例題 P-5-3. 合併排列法 [ZJ a233: 排序法~~~ 挑戰極限](https://zerojudge.tw/ShowProblem?problemid=a233) + [合併排序法](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E9%80%B2%E9%9A%8E-%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F%E6%B3%95-6252651c6f7e)是一個利用分治的經典排序法。重點是如何將兩邊已經各自排好序的序列合併成一個？ - 直觀作法。 - 可以用一個臨時空間 temp[] 放置合併後的序列，j 指右邊已經處理到的位置，k 指 要放入 temp[] 的位置。對於每個左邊的元素 a[i]，先把右邊比 a[i] 小的 a[j] 複製 到 temp[]，然後再把 a[i] 複製到 temp[]。最後將 temp[] 中的內容拷貝回陣列原來位置。i 迴圈跑完後，右邊可能有剩下的，但是它們都已經在正確的位置上了，所以不需要處理。 + 合併排序法的時間複雜度是 O(nlog(n))，因為合併的部分需要的是 O(n)，所以複雜 度遞迴式為:T(n) = 2T(n/2) + O(n)。 ::: :::info [d064: 例題 P-5-4. 反序數量 (APCS201806)](https://judge.tcirc.tw/problem/d064) + 最簡單的方法是檢查所有數對(A[i],A[j])，時間複雜度 O(n^2^)。 + 以分治思維來考慮，要計算一個區間的反序數量，將區間平分為兩段，一個反序對的兩個數可能都在左邊或都在右邊，否則就是跨在左右兩邊。都在同一邊的可以遞迴解，如何計算跨左右兩邊？亦即就是對每一個左邊的元素 x，要算出右邊比 x 小的有幾個。 + 假設對左邊的每一個，去檢查右邊的每一個，會花 O(n^2^)，如何減少時間？假設我們將右邊排序，花 O(nlog(n))，然後每個左邊的 x 可以用二分搜就可算出右邊有多少個小於 x，這樣只要花 O(nlog(n)) 的時間就可以完成合併。根據分治複雜度 T(n) = 2T(n/2)+O(nlog(n))，T(n) 的結果是 O(nlog^2^(n))。(p.151 P_5_4_a.cpp) + 可不可以精益求精做到 O(nlog(n))呢？剛才是單邊排序，所以很多次的二分搜花了 O(nlog(n))。假設兩邊遞迴呼叫時，回傳都是排好序的，就可以不必寫二分搜了。因為連續二分搜不如一路爬過去。(p.152 P_5_4_b.cpp) + 雖然避掉了二分搜，但是要排序，所以合併階段還是花了 O(nlog(n))，整個程式的複 雜度還是 O(nlog^2^(n))並沒有降下來。再看看這個程式是不是有點熟悉？計算右邊有幾個比 a[i] 小的部分不就幾乎是在合併左右兩個排好序的陣列嗎，跟 P-5-3 的合併排序法非常類似。所以呼叫排序根本是不必要的，在合併兩個排好序的序列時，本來就幾乎在算反序數了，時間複雜度也跟 merge sort 一樣是 O(nlog(n))。 ::: :::warning [Q-5-5. 習題 Closest pair(同 P-4-15, 分治版) (@@)](https://judge.tcirc.tw/problem/d056) + 將點依照 X 座標排序後，將所有點均分為左右兩部分，以遞迴分別求出左右的最近距離取最小值，在合併階段要找出左右各一點的最小距離。假設目前已找到的最小距離是 d，X 為中值的點座標是(p,q)，那麼兩邊的點只有 X 座標在 [p-d, p+d] 區間的點需要計算。如果兩邊的點已經依照 Y 座標排序，對左邊的任一點 (x,y)，右邊的點中只有 Y 座標落在 [y-d, y+d] 區間的點需要計算與 (x,y) 的距離。 在 P-4-15 掃瞄線算法時，必須使用一個動態的資料結構在點逐步加入時來維持 Y 座標排序，但是使用分治時，利用 merge sort 類似的方法，只需要用簡單的陣列就可以做到了，時間複雜度一樣是 O(nlog(n))。 ::: :::info [d065: 例題 P-5-7. 大樓外牆廣告](https://judge.tcirc.tw/problem/d065) + [h084. 4. 牆上海報](https://zerojudge.tw/ShowProblem?problemid=h084)，都是大樓題，演算法大不同，題目要看仔細。 + 天真的解法是嘗試所有左右端區間 [i, j]，對於每個區間最大可能的高度是在此區間的最小樓高，對每一個區間都跑一個迴圈找最小高度，O(n^3^)。 + 類似 maximum subarray，可以對任一個固定左端 i，一個迴圈跑完所有可能的右端，過程中不斷的更新 prefix-minimum，O(n^2^)。 + 分治的問題是如何分割及合併。假設第 i 棟 大樓的高度 h[i] 是全部高度中最低的，那麼能跨 i 左右的最大矩形，他的水平位置是整個區間，高度就是 h[i]。既然其他的矩形都不可能跨過 i 的左右，可以將區間切割成左右兩塊，分別遞迴求解，在所有找到的解中最大的就是最後的解。 + 上面分治的時間複雜度遞迴式是 T(n) = T(i) + T(n-i-1) + O(n)，如果運氣好，每次切割左右都能較平均，總時間複雜度會是 O(nlog(n))。但如果不幸每次的最低點都在邊緣，例如原輸入高度是遞增或遞減的，時間複雜度會高到 O(n^2^)。除非每次找最小值都可以很快的查詢出來(少於O(n))才能改善，必需用到比較複雜的資料結構來做區間最小值查詢(RMQ, range minimum query)。(p.157 P_5_7_dcn2.cpp) + 分治要有好的效率，最好是能平均分割，如此一來，只要合併花的時間小於 O(n)，整體的複雜度就會降下來了。均勻切割成兩塊不是問題，中點一切就行，問題在如何合併？也就是找出跨中點的最大矩形。 + 假設目前要處理的區間範圍是[s, t-1]，中點是 m，那麼跨過中點矩形的高度顯然不能超過 h[m]。在高度不小於 h[m] 的條件下盡量延伸左右範圍直到不能延伸為止，也就是會找到一個區間 [i+1, j-1]，h[i]<h[m] 或者已達左邊界，而且 h[j]<h[m] 或者已達右邊界。這樣可以求得以高度為 h[m]的最大矩形。每一次嘗試逐步下降高度，然後再往外擴增範圍，因為要逐步下降，所以下一次的高度基本上是 max(h[i],h[j])，除非其中之一已超越邊界，那就取另一端。重複以上的步驟，我們會嘗試過區間內所有可能的最高高度，找到最大的矩形。在擴增範圍的過程中，i 只會由中點往左邊跑，而 j 只會從中點往右邊跑，所以合併的步驟只會花線性時間，整體的複雜度是 O(nlog(n))。 + 分治的合併階段考慮的是左右邊各一個區段，如果把他想成左邊的一個區段與右邊的一點如何合併解答，就會是掃描線演算法，時間複雜度 O(n)，請利用 stack 自行思考練習。 ::: 範例演練(stack)，維設一個遞增子序列。<font color="#fff"> 假設輸入 h = [2, 1, 5, 6, 2, 3] (n=6)。 1.處理後 h 陣列: [-1, 2, 1, 5, 6, 2, 3, 0] (索引 0 到 7) 2. 初始堆疊 inc: [0] 3. i = 1 (h=2): h[0] < h[1]，推入 1。inc: [0, 1]。 4. i = 2 (h=1): h[1] > h[2]，觸發 while。 - 彈出 1。高度 height = h[1] = 2。 - 寬度 = i - inc.top() - 1 = 2 - 0 - 1 = 1。 - 面積 = 2 * 1 = 2。largest = 2。 - 推入 2。inc: [0, 2]。 5. i = 3 (h=5): h[2] < h[3]，推入 3。inc: [0, 2, 3]。 6. i = 4 (h=6): h[3] < h[4]，推入 4。inc: [0, 2, 3, 4]。 7. i = 5 (h=2): h[4] > h[5]，觸發 while。 - 彈出 4。height = 6。寬度 = 5 - 3 - 1 = 1。面積 = 6。largest = 6。 - h[3] > h[5]，繼續 while。 - 彈出 3。height = 5。寬度 = 5 - 2 - 1 = 2。面積 = 10。largest = 10。 - 推入 5。inc: [0, 2, 5]。 8. i = 6 (h=3): h[5] < h[6]，推入 6。inc: [0, 2, 5, 6]。 9. i = 7 (h=0): 右哨兵 0 會將堆疊中所有剩餘的長條 6, 5, 2 全部彈出並計算面積。 - 彈出 6 (h=3)，寬度=7-5-1=1，面積=3。 - 彈出 5 (h=2)，寬度=7-2-1=4，面積=8。 - 彈出 2 (h=1)，寬度=7-0-1=6，面積=6。 10. 結束: 最終 largest 為 10。 </font> ### 5.3. 補充說明 + 很多分治演算法所解的問題都有其他版本的解法，甚至別的解法的複雜度還更好。從基本的道理上看，很多分治的做法可以轉換成掃描線演算法並不意外。分治法的重點在合併，也就是跨過左邊與右邊的解；而掃描線演算法是一點一點的逐步加入右邊的資料。 + 如果仔細去看合併排序法與插入排序法，可以這麼說，其實合併排序法就是一次處理一整批的插入排序法。但分治因為是整批的合併，所以每個成員參與合併的次數不會太多(典型是 log(n)次)，合併時即使不使用什麼高超的技巧或複雜的資料結構，最後還是可以得到不錯的整體複雜度。 + 反觀掃描線演算法，因為一次加入一個資料，所以前面處理的某些結構或部分結果不可以丟棄，因此通常需要有個資料結構來幫忙維護，尤有甚者，這個資料結構往往必須是動態的，因為結構會不斷的變動。也就是說，對於一些題目，如果用分治法，搭配簡單的陣列可能就可以做，但是如果用掃描線演算法就必須配備 STL 中的資料結構，甚至是 STL 中沒有的資料結構。 - 舉例來說，對於 Q-5-5(closest pair)，如果以掃描線算法來作，必須保持已經掃過的點以 Y 值排序，我們必須使用一個動態資料結構(如 STL 中的 multimap)，但是分治法就不需要了。以考試或比賽範圍來說，multimap 可能不在考試範圍，但是使用分治法並不需要，所以還是可以考。 - 另外一個例子是 P-5-4 的反序數量，將分治法的合併演算法稍加修改就可以解，如果用掃描線演算法，每次碰到 a[i]，必須找到前面有幾個數字大於 a[i]，很不幸的 STL 中並沒有一個資料結構可以很簡單做到這事情，所以很多程式競賽的選手幾乎都是用線段樹(segment tree)來做這件事。也就是說，如果用分治計算反序數只需要簡單的程式與陣列，但是用掃描線算法則必須裝備一個「頗為複雜」的資料結構(線段樹)。 <br/> ## 六、動態規劃 + 動態規劃(Dynamic Programming, DP)。其中 Programming 指「以表格紀錄」，而非現在常用的「寫程式」，所以 DP 的意思是以變動的表格來求解的方法。 + DP 的應用很廣，變化很多，在學術界也發展的很早，在程式競賽也用的非常多，並且有很多困難而精妙的(優化)方法。 ### 6.1. 基本原理 #### 6.1.1. 基本思維與步驟 + [動態規劃簡介](https://mropengate.blogspot.com/2015/01/algorithm-ch2-dynamic-programming.html) + [一個問題若能用 DP 求解，該問題含有以下三個性質](https://hackmd.io/@3xOSPTI6QMGdj6jgMMe08w/HknO-zmQI/https%3A%2F%2Fhackmd.io%2Fs%2FByfT8JZ9E#Week-9-Dynamic-Programming-%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83) - 最優子結構(optimal substructure)：一個問題的最優解，可以由其子問題的最優解組合而成。([分治與貪心法同樣有著這個特性](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-DP#%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83%E5%95%8F%E9%A1%8C%E7%9A%84%E7%89%B9%E6%80%A7)) - 重疊子問題(overlapping subproblem) - 無後效性：子問題的解一但確定，就不會受到更大的問題的求解決策影響。 + 規劃步驟 1. 定義子問題(狀態定義)。 - 定義存最佳解的 dp[i] 的 i 是什麼狀態。 2. 找出問題與子問題之間的遞迴關係(狀態轉移方程)。 - 思考 dp[i] 如何用已求得的 dp[i-1], dp[i-2] … 來計算，或思考已求得的 dp[i] 如何延伸去計算 dp[i+1], dp[i+2] …。 - 再思考狀態轉移方程時，要不斷催眠自己 dp[i] 已知道答案，才較容易得到問題與子問題之間的遞迴關係。 3. 規劃初始狀態及轉移順序，避免以遞迴的方式進行計算。(以空間換取時間) - dp[0] 設定初始值。 - 如果沒有第三個步驟，而只是以遞迴的方式寫程式，就會變成純遞迴方式，往往會遭遇到非常大的效率問題，所以也可以說 DP 就是要改善純遞迴的效率問題的技術。 + EX：小朋友上樓梯，每步可走一階或兩階，如果走到第 n 階有 f(n)種走法，輸入 n，計算 f(n)。 - 例如 n=3 時，走法有 1+1+1=3 或 1+2=3 或 2+1=3，一共 3種，f(n)=3。 - 遞迴關係式：$f(n) = \begin{cases} f(n-1) + f(n-2) & \text{if } n > 2 \\ n & \text{otherwise} \end{cases}$ - 以遞迴寫，時間複雜度約 O(1.6^n^)。 - 第三步驟，什麼樣的計算順序可以不需要遞迴？如果 n 從小往大算，就可以從表格中取出 f(n-1 )與 f(n-2) 來相加得到 f(n)。 #### 6.1.2. 狀態轉移 + DP子問題的遞迴關係式也有人稱為「狀態轉移」。子問題可以看成一個狀態，目前的狀態是根據之前的那些狀態，這樣的轉換關係就稱作狀態轉移。設計DP時，最重要的就是找出狀態轉移。之前將子問題看成「部分解」，在找部分解與更小的解之間的關係，這兩個講法只是描述的方式不一樣。 + 小朋友上樓梯問題的子問題是走到第 i 階，關係式 f(n)=f(n-1)+f(n-2)，所以狀態圖如下，也就是每個狀態由它的前兩個狀態轉移而來。 ![upload_55085cbf7398cf8a2f183c57f85a019d](https://hackmd.io/_uploads/Hy94PX2Xle.png) #### 6.1.3. 分類與複雜度 + 一個DP如果狀態有 O(n^x^) 而狀態轉移方程涉及 O(n^y^) 個狀態，一般可稱為 xDyD 的 DP。 + 小朋友上樓梯是 1D0D，因為有 n 個要算，每次算 f(i) 只涉及 2 個 f(i-1) 與 f(i-2)。 + 方格路徑的問題則是 2D0D，因為有 n^2^(假設 m=n)個要算，每次只需要 2 個(左方與上方)。 + 當一個 xDyD 的 DP，如果沒有優化，時間複雜度就是 O(n^x+y^)。一般來說若 y=0 時比較簡單，因為遞迴式單純，套個迴圈依序計算就是了。y=1 的 DP 題目通常存在某種優化或需要某些資料結構幫忙，會比較難。 #### 6.1.4. Top-down memoization + 前面設計 DP 算法的步驟，基本上要先找出遞迴式，然後找出計算順序來避免遞迴。這算是標準的 DP，也稱為 Bottom-up 的 DP。另外有一種實現 DP 的方式是不找計算順序，直接依照遞迴式寫遞迴，但是因為一定要避免遞迴的重複計算，所以採取了一些步驟，這種實現的方式稱為 top-down memoization 的 DP。 + top-down memoization 就是再找到遞迴式之後，直接寫成遞迴版本的程式，但要加上三個動作：開一個表格當作小抄，用來記錄計算過的結果，表格初值設為某個不可能的值，用以辨識是否曾經算過。在遞迴之前，先偷看一下小抄是否曾經算過，如果小抄上有答案(已經算過)，則直接回傳答案。如果小抄上沒有，就遞迴呼叫，但計算完畢回傳前，要把它記在小抄上。(p.167) + 雖然 Top-down 的 DP 速度相同，但基本上是個偷懶的方法，如果計算順序不難找，還是寫迴圈版，不要過分偷懶，因為遞迴的深度有一定的限制，超過限制會導致執行階段的錯誤。在計算順序比較不好找或者比較麻煩時，而且系統是允許的狀況下，就採用 top-down 吧！最常見的情形就是 Tree 的 DP，幾乎參加比賽的選手都寫遞迴的 DFS 版本，因為迴圈版的要找 bottom-up 順序(如 P-3-1)，比較麻煩。所以兩種都要會，可以偷懶的時候才偷懶。 ### 6.2. 例題與習題 #### 6.2.1. 1D0D :::info [d066: 例題 P-6-1. 小朋友上樓梯最小成本](https://judge.tcirc.tw/problem/d066) - 假設踩在第 i 階的扣分是 cost[i]。 - 狀態定義： dp[i] 是走到第 i 階的最小扣分。 - 狀態轉移方程：dp[i] = cost[i] + min(c[i-1], c[i-2]) for c>2 - 初始條件：dp[1]=cost[1]、dp[2]=cost[2]。 ::: :::info [d067: 例題 P-6-2. 不連續的表演酬勞](https://judge.tcirc.tw/problem/d067) + 每天可以獲得的酬勞放在一維陣列 p[] 中。 + 狀態定義： dp[i] 是前 i 天可以獲得的最大報酬。 + 狀態轉移方程 - 如果第 i 天不選，前 i 天的獲利就是前 i-1 天的獲利 dp[i]=dp[i-1]。 - 如果第 i 天要選，可以獲利 p[i]，但是第 i-1 天就不可以選，因此最大的獲利是 p[i]+dp[i-2]。 - dp[i]=max(dp[i-1], p[i]+dp[i-2])。 + 初始條件：dp[0]=p[0]，dp[1]=max(p[0],p[1])。 ::: :::info [d068: 例題 P-6-3. 最小監控鄰居的成本](https://judge.tcirc.tw/problem/d068) + 類似前一題定義 dp[i] 為前 i 個的最小成本，遞迴式？ - 如果 dp[i-1] 的值是有挑選到 i-1 的，那麼第 i 個點已經被監控到，dp[i]=dp[i-1]。 - 如果 dp[i-1] 的值來自沒有挑選到 i-1，那麼第 i 點變成非挑不可，dp[i]=cost[i]+dp[i-1]，但dp[i-1]不知道 i-1 是否已經有挑選。 + 改變子問題的定義：設 dp[i] 是前 i 個點的最小監控成本，而且最後一點選在 i。 - 前面的點雖然不確定那些點一定要挑，但是不可能第 i-1、i-2 與 i-3 都沒有挑選，否則 i-2 就沒被監控了。 - dp[i] = c[i] + min(dp[i-1], dp[i-2], dp[i-3]) for i>2 + 遞迴式列不出來時，可以把子問題加條件，或將子問題依照不同的條件再進一步分類，例如本題也可以思考將前 i 個解分成兩類：dp0[i] 代表第 i 個沒選，dp1[i] 代表第 i 個有選。 - dp0[i] = dp1[i-1]; // i 沒選，i-1 一定要選 - dp1[i] = c[i] + min( min(dp0[i-2], dp1[i-2]), dp1[i-1] ); * 第 i 個有選時又可分 A、B 2 個策略，選兩者中成本最小者。 * 策略 A：利用 i 來覆蓋 i-1，那麼只需要確保 0 到 i-2 的所有點都已經被覆蓋就好了（i-1不用考慮）。所以 dp1[i] = c[i] + min(dp0[i-2], dp1[i-2])。 * 策略 B：利用選 i-1 來覆蓋 i-2（i-2不用考慮）。所以 dp1[i] = c[i] + dp1[i-1]。 ::: :::warning [d072: 習題 Q-6-4. 闖關二選一](https://judge.tcirc.tw/problem/d072) + 以狀態轉移的方式來思考，有 n 個關卡要通過，每個關卡通過的成本只跟上一關有關(跟更早的無關)，設 dp[i][j] 為第i關、第j種狀態的最低成本(i<=n，j=0或1)。所以 dp[i][0] 是 i 關選擇在數字一的最佳解，dp[i][1] 則是選數字二的最佳解。 + 如果這一關停留在數字一： dp[i][0] = min(上關選數字一 + 這關選數字一，上關選數字二 + 這關選數字一) 如果這一關停留在數字二： dp[i][1] = min(上關選數字一 + 此關選數字二，上關選數字二 + 此關選數字二) ![upload_d10a232e34f6dea13d00379f23ce497d](https://hackmd.io/_uploads/HyAkYJaXee.png) ::: :::warning [d073: 習題 Q-6-5. 二維最大子矩陣](https://judge.tcirc.tw/problem/d073) + 單前綴和：[O(n^4^)](http://chchwy.blogspot.tw/2008/11/acm108-maximum-sum-ac.html)，94%。 - 前綴和 ![](https://hackmd.io/_uploads/r1vpzDlSn.png) **➜** ![](https://hackmd.io/_uploads/BJMRGvlr3.png) - (r1,c1)~(r2,c2)的和為：a[r2][c2]-a[r2][c1-1]-a[r1-1][c2]+a[r1-1][c1-1] |[0][0] |[0][1]|[0][2] |[0][3] |[0][4]|[0][5] | |:----: |:----:|:----: |:----: |:----:|:----: | |**[1][0]**| | | | | | |**[2][0]**| |[r1-1][c1-1]| | |[r1-1][c2]| |**[3][0]**| | |[r1][c1]| | | |**[4][0]**| | | | | | |**[5][0]**| |[r2][c1-1] | | |[r2][c2] | + P-4-13 變化為二維：O(n^3^)。 - 先計算每一欄的前綴和 <table border="1"> <tr> <td>2</td> <td>-2</td> <td>3</td> <td>3</td> <td rowspan="3">⮕</td> <td>2</td> <td>-2</td> <td>3</td> <td>3</td> </tr> <tr> <td>-6</td> <td>5</td> <td>2</td> <td>-8</td> <td>-4</td> <td>3</td> <td>5</td> <td>-5</td> </tr> <tr> <td>3</td> <td>7</td> <td>-2</td> <td>4</td> <td>-1</td> <td>10</td> <td>3</td> <td>-1</td> </tr> </table> - 計算第 i 到 j 行的各種組合，以範例輸入 1 為例，假設i=2, j=3時。(網底為原始數字計算範圍) <table border="1"> <tr> <td></td> <td>k</td> <td></td> <td></td> <td></td> <td rowspan="5">➡️</td> <td></td> <td></td> <td>k</td> <td></td> <td></td> </tr> <tr> <td></td> <td>2</td> <td>-2</td> <td>3</td> <td>3</td> <td></td> <td>2</td> <td>-2</td> <td>3</td> <td>3</td> </tr> <tr> <td>i</td> <td style="background-color: #ffcccc;">-4</td> <td>3</td> <td>5</td> <td>-5</td> <td>i</td> <td>-4</td> <td style="background-color: #ffcccc;">-3</td> <td>5</td> <td>-5</td> </tr> <tr> <td>j</td> <td style="background-color: #ffcccc;">-1</td> <td>10</td> <td>3</td> <td>-1</td> <td>j</td> <td>-1</td> <td style="background-color: #ffcccc;">10</td> <td>3</td> <td>-1</td> </tr> <tr> <td colspan="5">sum=max(sum,0)+dp[j][k]-dp[i-1][k] =max(0,0)+(-1)-2=-3</td> <td colspan="5">sum=max(sum,0)+dp[j][k]-dp[i-1][k] =max(-2,0)+10-(-2)=12</td> </tr> <tr> <td colspan="11" style="text-align:center;">↙️</td> </tr> <tr> <td></td> <td></td> <td></td> <td>k</td> <td></td> <td rowspan="5">➡️</td> <td></td> <td></td> <td></td> <td></td> <td>k</td> </tr> <tr> <td></td> <td>2</td> <td>-2</td> <td>3</td> <td>3</td> <td></td> <td>2</td> <td>-2</td> <td>3</td> <td>3</td> </tr> <tr> <td>i</td> <td>-4</td> <td style="background-color: #ffcccc;">3</td> <td style="background-color: #ffcccc;">5</td> <td>-5</td> <td>i</td> <td>-4</td> <td style="background-color: #ffcccc;">-3</td> <td style="background-color: #ffcccc;">5</td> <td style="background-color: #ffcccc;">-5</td> </tr> <tr> <td>j</td> <td>-1</td> <td style="background-color: #ffcccc;">10</td> <td style="background-color: #ffcccc;">3</td> <td>-1</td> <td>j</td> <td>-1</td> <td style="background-color: #ffcccc;">10</td> <td style="background-color: #ffcccc;">3</td> <td style="background-color: #ffcccc;">-1</td> </tr> <tr> <td colspan="5">sum=max(sum,0)+dp[j][k]-dp[i-1][k] =max(12,0)+3-3=12</td> <td colspan="5">sum=max(sum,0)+dp[j][k]-dp[i-1][k] =max(12,0)+(-1)-3=8</td> </tr> </table> ::: #### 6.2.2. 2D0D + 1D0D DP 的子問題，往往都是以一個整數由小到大編號。2D0D DP 的子問題通常是由一個二維陣列來編號。 :::info [d069: 例題 P-6-6. 方格棋盤路線](https://judge.tcirc.tw/problem/d069) + 若 𝑎[𝑖][𝑗] 是該格子的分數。 + 狀態定義：𝑓[𝑖][𝑗] 是走到位置 (𝑖,𝑗) 所能獲得的最大得分。 + 狀態轉移方程：$𝑓[𝑖][𝑗]=max(𝑓[𝑖−1][𝑗],\ 𝑓[𝑖][𝑗−1])+𝑎[𝑖][𝑗]$ + 初始條件：因為最上面一列只能從左方走過來，最左邊一欄只能從上方走過來，所以對這兩個邊界單獨計算。 ::: :::info [d070: 例題 P-6-7. LCS](https://judge.tcirc.tw/problem/d070) + LCS(Longest Common Subsequence，最長共同子序列)是序列分析的重要問題，一個序列的子序列是指將其中某些元素刪除後所得到的序列，字串可以看成字母組成的序列，以 ”algorithm” 為例，”algtm” 與 ”lgh” 都是它的子序列，但是”agl”則不是(不可以調整位置重新排列)。輸入兩序列，LCS要找一個最長的序列，它是兩輸入序列的共同子序列。([LCS Demo](https://www.youtube.com/watch?v=LRLc-C8lFOQ)) + 暴力搜尋不可行，一個長度 n 的序列有 2^n^ 個子序列，因為每一個位置都可以刪除或不刪除。 + 狀態定義 - 比對兩字串最普通的方式是從前往後比對，定義 lcs(i, j) 為 x 的前 i 個字元（x[0]~x[i-1]），與 y 的前 j 個字元（y[0]~y[j-1]），最長共同子序列的長度。 - x 字串的 index 由 0 開始，長度 i 的最元素為x[i-1]。 + 狀態轉移方程 - $$ lcs(i,j)= \begin{cases} 0 \qquad\qquad\qquad\qquad\qquad\qquad\qquad\ \ \ if \ i=0 \ or \ j=0 \\[2ex] lcs(i-1,\ j-1)+1\qquad\qquad\qquad\ \ if \ x[i]=y[j] \\[2ex] max(lcs(i-1,j),\ lcs(i,j-1))\qquad otherwise \end{cases}\qquad\qquad\qquad\qquad\qquad\qquad\qquad $$ + 初始條件：若其中一個字串的長度為 0 與另一字串的 LCS 當然是空字串，所以 lcs[i][0]=lcs[0][j]=0。 + [實作步驟說明](https://www.youtube.com/watch?v=uX-PJiNVHrs&t=17m33s)：把 lcs[][] 看成一個表格，看 x[i]與 y[j]是否相等，每一個格子只跟左方、上方與左上方的格子有關。 + 二維的問題有的時候會有空間用量太大的麻煩。如果兩個字串長度到 1 萬，時間或許還可以接受，但是空間會出現不足的問題。如果只是要算 LCS 長度，計算 lcs[i][j] 時，我們只需要第 i 列與前一列就足夠了，並不需要一直留著整張表格。所以有一個節省記憶體的方法，宣告一個 2*N 的表格，奇數回合從第 0 列算到第 1 列，偶數回合從第 1 列算回第 0 列，這個方式有人稱為滾動陣列。自行練習 p.179 滾動陣列的做法。 ::: :::warning [d074: 習題 Q-6-8. Local alignment](https://judge.tcirc.tw/problem/d074) + 計算 global alignment 與 LCS 很類似，計算 local alignment 與 global 的差別在於，如果前面的分數不好，可以放棄繼承，此外最大分數未必出現在最後的位置。 + 當 x[i]=y[j]時，dp[i][j] = dp[i-1][j-1]+8 當 x[i]!=y[j]時, dp[i][j] = max(dp[i-1][j]-3, dp[i][j-1]-3, dp[i-1][j-1]-5) dp[i-1][j] 和 dp[i][j-1] 為字母與空白對應 -3 分 dp[i-1][j-1] 為兩字母相異 -5 分 ::: :::warning [ZJ e828. 3.猴子打字遊戲 (Typing)](https://zerojudge.tw/ShowProblem?problemid=e828) + [編輯距離(Edit Distance)](https://www.youtube.com/watch?v=_g8CJw6J1Jo)是計算兩個字串之間，透過插入、刪除、替換等操作所需要的最少編輯步數。也叫做 Levenshtein 距離問題。 + 狀態轉移方程 dp[i][j] = min( 　dp[i][j-1] + 2, // 插入 　dp[i-1][j] + 2, // 刪除 　dp[i-1][j-1] + 3 // 替換 ) ::: :::info [d071: 例題 P-6-9. 大賣場免費大搬家](https://judge.tcirc.tw/problem/d071) + 0/1-knapsack 經典題。 + 相對於物品可分割背包問題，在選擇物品時，要麼完整地選擇，要麼不選擇，不可以只拿物品的一部份(物品不可分割)。 - Greedy 不行，假設背包負重 30kg，會得到 190(50+140)，但最大價值為 200(60+140)。 |物品|重量|價值|價值/重量比| |:-:|:-:|:-:|:-:| |1 |5 |50 |10| |2 |10 |60 |6 | |3 |20 |140|7 | - 窮舉法會太多狀況，n 個物品，每個物品可以選擇拿或不拿，會有 [2^n^ 種可能性](https://www.youtube.com/watch?v=edsxbUr9uKk) 種可能性要考慮(例如 ZJ d637，n=10000)。 + 假設將子問題定義成 dp[i] 是考慮前 i 個物品的最佳解，在設法列出遞迴式時會遭遇到困難，主要因素是加入一個新的物品時，前面找出來的最佳解可能全部改變。例如考慮前 5 項時，最佳解可能是挑第 1 與第 2 件，但是第六項納入考慮時，可能最佳解變成第 6 與第 3、4 項。這樣找不到子問題最佳解之間的關係，所以是個失敗的定義。前面說過一個原則，找不出的時候常用的手法就是加條件，也可以說把解進一步分類。 + 考慮加入第二個條件：重量。令 dp[i][j] 表示只考慮拿前 i 個物品，放入最大負重為 j 的背包時，可以得到的最大價值。 + 狀態轉移方程 - 假設第 i 項物品的重量為 w[i]，價值為 v[i]。 - 如果 w[i]>j，根本不可能挑選。 - 如果拿第 i 項物品，背包重量剩 j-w[i] (可以從i-1項挑選)，亦即在負重 j 時，第 i 個物品不拿時的價值，與拿了第 i 個物品時的價值，選擇較好的那個。 - $$ dp(i,\ j)=\begin{cases} 0 \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\ \ \ if \ i=0 \ or \ j=0 \\[2ex] dp(i-1,\ j) \qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\ if \ w[i]> j\\[2ex] max(\ dp(i-1,\ j),\ dp(i-1,\ j-w[i]) + v[i]\ )\quad otherwise \qquad\qquad\qquad\qquad\qquad \end{cases} $$ + 初始條件：沒有物品或重量限制 0 的時候的最大價值都是 0。 + 實作步驟：dp[][] 看成一個表格，每一個格子只跟上方與左上方的某個格子有關。 ![](https://i.imgur.com/W3NOKXG.png) + 空間優化：更新藍色格子只需要紅色格子的資料。 ![](https://i.imgur.com/6IPdibf.png) - 狀態定義 dp(j) 為背包重量為 j 時的最大價值。 - 對第 i 個物品，考慮不拿或拿，狀態轉移方程為 dp(j)=max(dp(j), dp(j-w[i])+v[i]) - 如果如原本由左->右更新表格，會有什麼問題？ 若 dp(j−w[i]) 已經拿 i 物品，更新到 dp(j) 時，拿 i 物品也有較大價值，因為 dp(j)=dp(j−w[i])+v[i]，dp[j] 相當於拿了兩次 i 物品，違反物品只能拿一次的要求。 調整 j 由右->左更新表格，則可避免物品重複拿。 ::: :::warning [d075: 習題 Q-6-10. 置物櫃出租 (APCS201810)](https://judge.tcirc.tw/problem/d075) + 0/1-knapsack + f[i] 是第 i 位客戶的租容量(收益和容量相等)，dp[j] 是在出租 j 個容量時的最大收益。計算剩下空間的最大收益，王老先生最小的損失利益=總收益-剩下空間的最大收益。 - dp[j] = max(dp[j], dp[j-a[i]] + a[i]) ::: :::warning [ZJ d904: 換零錢](https://zerojudge.tw/ShowProblem?problemid=d904) + 若每個硬幣面額 c[i]，dp[i] 為換金額 i 的最少硬幣數目。 + 狀態轉移方程：dp[j] = min(dp[j], dp[j–c[i]]+1)。 - 檢查使用一個新的硬幣面額時，金額 j 是否可以用更少的硬幣換出來。 - 零錢可重複，檢查金額時，不需大到小檢查。 ::: #### 6.2.3. 1D1D + 1D1D 的 DP 指有 O(n) 個子問題(狀態)，但每一個子問題的計算需要 O(n) 個子問題 的結果，也就是說一個狀態會牽涉 O(n) 個前置狀態。如果直接計算，時間複雜度就是 O(n^2^)，不過很多 1D1D 問題的計算都會利用資料結構或問題的特性來降低複雜度。 :::info [d076: 例題 P-6-11. Catalan number](https://judge.tcirc.tw/problem/d076) + C~n~ = C~0~⋅C~n−1~ + C~1~⋅C~n−2~ + ⋯ + C~n−1~⋅C~0~ ::: :::warning [d084: 習題 Q-6-12. 楊鐵心做 1 休 K](https://judge.tcirc.tw/problem/d084) + P-6-2 的推廣 + 設 dp[i] 是前 i 天可以獲得的最大報酬，dp[i]=max(dp[i-k-1]+當天報酬, dp[i-1])。 + dp 前 k 天的初值為當天之前報酬的最大值。 ::: :::info [d077: 例題 P-6-13. 周伯通的基地台 (@@)](https://judge.tcirc.tw/problem/d077) + 若 k=1，這一題就是 P-6-3。令 dp(i) 表示可以服務 i 之前的所有位置而最後一個站架在 i 最小成本，因為與前一站的距離不可超過 2k+1，所以前一站必然在[i-2k-1, i-1]。 + 狀態轉移方程 dp(i)=c[i] + min{dp(j): i-2k-2 < j < i} for i > k+1; and dp(i)=c[i] for i <= k+1 最後的解在 min{dp(i): n-k <= i <= n} + 如果直接做, 需要 O(kn)的時間, 所以要設法很快的求得區間最小值，有一些比較高階的資料結構可以每次求的區間最小值(RMQ, range minimum query)，目前超出範圍，可以用 P-3-8 例題中(在一個滑動的視窗中每次找出最小值)的技巧。 + 以 deque O(n)、PQ O(nlog(n)實作。(p.188-p.189) ::: :::warning [d085: 習題 Q-6-14. K 次買賣 (106 高中全國賽 subtask)](https://judge.tcirc.tw/problem/d085) + P-4-12 的推廣型。 + 狀態定義 - dp_no_hold[i][j]：表示在考慮到第 i 天的價格為止（從第 1 天到第 i 天），且已經完成了 j 次完整的買賣操作，並且在第 i 天不持有任何商品的情況下，所能獲得的最大總利潤。 - dp_hold[i][j]：表示在考慮到第 i 天的價格為止，且已經進行了 j 次「買入」操作（當前手上有一支個商品），所能獲得的最大總利潤。 - 這裡的 j 對於 dp_hold 而言，表示的是第 j 次買入的完成，不代表第 j 次交易已經完全結束（因為還沒賣出）。但在 dp_no_hold 中，j 表示的是第 j 次交易的完成（買入和賣出都完成了）。 + 狀態轉移方程 - 計算 dp_no_hold[i][j] 有兩種可能： * 第 i-1 天結束時就已經不持有商品，且已經完成了 j 次交易。這意味著第 i 天沒有進行任何買賣操作。 ⟹ dp_no_hold[i−1][j] * 第 i-1 天結束時持有商品（且已進行 j 次買入），並在第 i 天賣出，從而完成了第 j 次交易。利潤會增加當天價格 prices[i]。 ⟹ dp_hold[i−1][j] + prices[i] * 因此 dp_no_hold[i][j] = max(dp_no_hold[i−1][j], dp_hold[i−1][j]+prices[i]) - 計算 dp_hold[i][j] 有兩種可能： * 第 i-1 天結束時就已經持有商品（且已進行 j 次買入）。這意味著第 i 天沒有進行任何操作。 ⟹ dp_hold[i−1][j] * 第 i-1 天結束時不持有商品（且已完成 j-1 次交易），並在第 i 天買入，從而開始了第 j 次買入操作。利潤會減少當天價格 prices[i]。 ⟹ dp_no_hold[i−1][j−1]−prices[i−1] * 因此 dp_hold[i][j] = max(dp_hold[i−1][j], dp_no_hold[i−1][j−1]−prices[i−1]) + 初始條件 - dp_no_hold 和 dp_hold 都初始化為一個極小的負數 (-INF)。 表示這些狀態在預設情況下是無效的，除非被有效的轉移路徑更新。 - dp_no_hold[0][0] = 0，表示在「第 0 天」時（即還未開始），進行了 0 次交易，且不持有商品，此時的總利潤為 0。這是我們動態規劃的起點。 - 對於所有 i 從 1 到 n，dp_no_hold[i][0] = 0，表示在任何一天結束時，選擇不進行任何交易（即完成了 0 次交易），那麼利潤永遠是 0。 + 在遍歷完所有天數 (到第 N 天) 和所有可能的交易次數 (到 K 次) 後，我們需要找到在第 N 天結束時所能獲得的最大利潤。這表示最終不能持有商品。$\max_{0 \le j \le K} (dp\_no\_hold[N][j])$ 會從所有完成 0 到 K 次交易、且在最後一天不持有股票的狀態中，選出最大的利潤。 + 思考空間優化的方法。 ::: :::info [d078: 例題 P-6-15. 一覽衆山小](https://judge.tcirc.tw/problem/d078) + 一個序列的子序列是指可以任意挑選某些成員，但是不可以交換他們的前後順序，也可以說是刪除某些元素。本題是要在一個數列中找到一個最長的遞增子序列 LIS (longest Increasing subsequence)，1D1D經典題。[演算法筆記-LIS](http://web.ntnu.edu.tw/~algo/Subsequence.html)。 + 狀態定義：dp[i] 表示以 s[i] 為結尾的最長遞增子序列長度(s[0]~s[i]的 LIS 長度) + 狀態轉移方程：dp[i] = max{dp[j]+1：0<=j<i and s[j]<s[i]} + 範例：假設序列為 2 7 4 1 8 3。 | s[] | 2 | 7 | 4 | 1 | 8 | 3 | |:------------------:|:---:|:---:|:---:|:---:|:---:|:---:| | LIS 的元素 | 2 | 2 7 | 2 4 | 1 | 2 4 8| 1 3 | | dp 陣列值 (s[]為結尾的LIS 長度) | 1 | | | | | | | 7 可接在 2 後 | 1 | 2 | | | | | | 4 可接在 2 後 | 1 | 2 | 2 | | | | | 1 無法接在任何數後 | 1 | 2 | 2 | 1 | | | | 8 可接在 4 後 | 1 | 2 | 2 | 1 | 3 | | | 3 可接在 1 後 | 1 | 2 | 2 | 1 | 3 | 2 | + 上面的做法，對每個 i 點，都要往前搜尋所有的 j 點，時間複雜度為O(n^2^)，如何加速？(省略不必要的計算)。 如果 s[i]<=s[j] (i>j)，但 dp[i]>=dp[j]，表示s[i]的值比較小，但有比較長的 LIS。那麼可以接在 s[j] 後面的一定也可以接在 s[i] 後面。例如上一個例子，2 4 可以取代 2 7，後面如果有 5 可發展出更長 的 LIS。所以對之後的數字，2 7 不需要再檢查。 + Q：如果刪除沒有用的子問題結果，會剩下甚麼呢？ A：每一種 LIS 長度只會有一個狀態被留下來$\Rightarrow$ 結尾數值最小的狀態。 + 以陣列 last[L] 記錄 LIS 長度為 L 的最後一個元素(選值最小的，讓後續數字有機會發展出更長的 LIS) + 範例：假設序列為 2 8 6 7 1 3 4 9。 | LIS 長度 | 1 | 2 | 3 | 4 |概念| |:--------------:|:---:|:---:|:---:|:---:|:---| |last 陣列|2| | | |s[0]=2 | | |2|8<br />(2 8)| | |s[1]=8 | | |2|6<br />(2 6)| | |s[2]=6，26 取代 28| | |2|6|7<br />(2 6 7)| |s[3]=7，7可加在6後，變成長度3| | |1|6|7| |s[4]=1| | |1|3<br />(1 3)|7| |s[5]=3，3可以取代6(13->26)，<br />**找到第一個>=3的元素並取代**| | |1|3|4<br />(1 3 4)| |s[6]=4，134 取代 267，<br />找到第一個>=4的元素並取代| | |1|3|4|9<br />(1 3 4 9)|s[7]=9，找不到直接加在最後面| + last 陣列的元素是單調遞增的，要找 s[i] 可以接在誰後面時，不用循序找，可以用二分搜加速。分別練習自己寫二分搜(p.192)和使用lower_bound()。 ::: :::warning [ZJ f608: 4. 飛黃騰達](https://zerojudge.tw/ShowProblem?problemid=f608) + [最長嚴格遞增子序列(LIS)的變形](https://www.youtube.com/watch?v=vLS3fCeGpeI) - 將所有點依 x 座標排序後，每個點的 y 座標可看成一個整數序列。對任意 i<j 若y[i]<=y[j]，表示 i 點可以走到 j 點，所以每一種走法就是一個非遞減子序列，本題就是要找一個最長的非遞減子序列(Longest Non-Decreasing Subsequence)。 - 範例 | ![](https://hackmd.io/_uploads/SkEOI64kle.png =235x)<br> $\bf\fbox 1$ 5 $\bf\fbox 1$ $\bf\fbox 3$ 2 $\bf\fbox 4$ $\bf\fbox 4$ 6 3 $\bf\fbox 5$ 4<br> $\bf\fbox 1$ 5 $\bf\fbox 1$ 3 $\bf\fbox 2$ $\bf\fbox 4$ $\bf\fbox 4$ $\bf\fbox 6$ 3 5 4<br>$\vdots$| 11<br>1 1<br>1 5<br>2 1<br>2 3<br>3 2<br>3 4<br>4 4<br>4 6<br>5 3<br>5 5<br>6 4<br>Ans：6| | :--------: | :-------- | - 飛黃可以向上或『向右』移動，y 座標相等可以加到非遞減子序列。 LIS 在 last 陣列中尋找第一個『>=』(lower_bound) 的元素，這裏要改為尋找第一個 『>』(upper_bound) 的元素(數值相同要保留，不要覆蓋掉)。 ![](https://i.imgur.com/kRdyVp9.png =150x) + 排序時 x 相等則比較 y，可以用 pair 來記錄點，預設即會這樣比較。 + [C++ 17 結構化綁定](https://zh-blog.logan.tw/2019/10/29/cxx-17-structured-binding/) ::: :::warning [d118: 例題 P-6-16. 山寨華山論劍](https://judge.tcirc.tw/problem/d118) + P-4-4 加權版本。weighted activity selection problem 經典題。 + 沒權重的時候是用貪心法則來求解，挑選最早結束的活動。但是在加權版本時，範例一告訴你，挑最早結束的是錯的，範例二告訴你，挑權重最大的也是錯的。 + 假設線段放在$seg[\ ]$中，先讓線段依照右端排序，假設第 $i$ 個線段的區間是 $[L[i], R[i]]$，權重是 $w[i]$。定義 $dp[i]$ 是前 $i$ 個線段的最佳解(最大權重和)。第 $i$ 個線段可能挑或不挑。 - 不挑：$dp[i]=dp[i-1]$ - 挑：跟它重疊的都不能挑，也就是說右端落在 $seg[i]$ 範圍內的線段都要剔除。$\max\{dp[j]: R[j] < L[i]\}$。因為 $dp[]$ 顯然是非下降的，所以我們要找的 $dp[j]$ 就是滿足右端小於 $L[i]$ 的最大編號 $j$。 + 狀態轉移方程：$dp[i]= \max\{dp[i-1], w[i]+dp[j]\}$，其中$j=\max\{x: R[x] < L[i]\}$。 + 練習用 O(n^2^) 和 lower_bound() 實作。(p.195-p.196) ::: #### 6.2.4. 2D1D與其他 :::info [d079: 例題 P-6-17. 切棍子](https://judge.tcirc.tw/problem/d079) + 狀態定義 - $cost(i, j)$ 表示第 i 點到第 j 點這段的最低切割成本。 - 以座標 0 與 L 當作第 0 與第 n+1 點，即求 $cost(0, n+1)$。 + 狀態轉移方程 - 對任意 $i<j$，$cost(i,j)$ 就是一個子問題，所以有 $O(n^2)$ 個子問題。 - $$ cost(i,\ j)=\begin{cases} 0 \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad if \ j=i+1 \\[2ex] \min\limits_{i<k<j}\{\ cost(i,\ k) + cost(k,\ j) \ \} + p[j]-p[i] \quad otherwise \qquad\qquad\qquad\qquad\qquad \end{cases} $$ + 範例 ![](https://hackmd.io/_uploads/ByWp3AdUle.jpg =500x) + 練習 top-down 和 bottom-up 2種寫法(p.199)。 ::: :::warning [d086: 習題 Q-6-18. 矩陣乘法鏈](https://judge.tcirc.tw/problem/d086) + [矩陣相乘次序(Matrix Chain Multiplication)](https://web.ntnu.edu.tw/~algo/DynamicProgramming.html#4) + dp(i, j)為從第 i 個矩陣乘到第 j 個矩陣，最少的相乘次數。 + r[i]為第 i 個矩陣的列數，c[i]為第 i 個矩陣的欄數。 + $$ dp(i, j) = \min\limits_{i\le k<j} \{ dp(i, k) + dp(k+1, j) + r[i]*c[k]*c[j] \} \qquad\qquad\qquad\qquad\qquad\qquad\qquad$$ ::: :::warning [ZJ m934. 4. 合併成本](https://zerojudge.tw/ShowProblem?problemid=m934) + $$ dp(i, j) = \min\limits_{i\le k<j} \{ dp(i, k) + dp(k+1, j) + |sum(i,k)-sum(k+1,j)| \} \qquad\qquad\qquad\qquad\qquad\qquad\qquad$$ + [解題參考](https://hackmd.io/@bangyewu/SkKxG8Oua?fbclid=IwAR09nvTMNtD9ilT1bdtXLjSgTgr-tGe9OxEoodT9bF0xlSYmcgmZmB4etQA) ::: ### 6.3. 進階題(*) + DP 的題目很多，有些在競賽中出現的往往需要某些特殊資料結構與特別的優化技巧。 :::info [d089: 習題 Q-6-25. 貨郎問題 (@@)](https://judge.tcirc.tw/problem/d089) + 旅行推銷員問題，一個人要把 n 個城市都走一遍再回到起點，題目中說，對任兩個城市來說，繞經第三地並不會比較近，因此單純的可以看作是一個找排列的方式，暴力解法是枚舉所有可能的城市排列，時間複雜度為 O(n!)，對於 n=16 來說太大了。 + 狀態定義 - 需要記錄當前已經訪問過哪些城市，可以透過一個二進位狀態壓縮 mask，mask 為一個整數，在其二進位的表示中，如果第 i 位是 1，表示城市 i 已經被訪問過；如果為 0，則表示城市 i 尚未訪問。 - dp[mask][curr]：表示從起點 m 出發，訪問過 mask 中所有為 1 的城市，並且最後停留在城市 curr 的最短路徑長度。 + 狀態轉移方程 - 假設我們目前位於城市 curr，並且已經訪問過的城市集合是 mask。現在我們要從 curr 移動到一個尚未訪問過的城市 next_city。 - dp[mask | (1≪next_city)][next_city] = min( dp[mask | (1≪next_city)][next_city], dp[mask][curr] + d[curr][next_city]) - mask | (1 << next_city) 表示在原來的 mask 基礎上，將 next_city 這個城市也加入到已訪問的集合中。遍歷所有可能的 next_city，找最小的值。 + 初始條件：dp[1≪m][m]=0：表示從城市 m 出發，只訪問了城市 m 本身，停留在城市 m，路徑長度為 0。 + 最終答案：dp[(1≪n)−1][m] 這表示從城市 m 出發，訪問了所有城市，最後回到城市 m 的最短路徑長度。 ::: <br/> ## 七、基本圖論演算法 ### 7.1. 基本觀念與名詞 + 自行閱讀 p.219-p.222 ### 7.2. 資料結構與基本演算法 #### 7.2.1. 資料結構 + 儲存圖的資料結構常用有兩種：鄰接矩陣(adjacency matrix)與鄰接串列(adjacency list)。 + [鄰接矩陣表示法(Adjacency Matrix)](http://web.ntnu.edu.tw/~algo/Graph.html#3) - 最大的好處是簡單方便。 - 最大的麻煩是空間與時間效率。一個$n$個點的簡單圖，鄰接矩陣所需要的空間是$O(n^2)$。如果是 sparse graph，矩陣裡面大部分都是 0。 - 補充練習：(DFS) [d908: 4. 最佳路徑](https://zerojudge.tw/ShowProblem?problemid=d908) + [鄰接串列表示法(Adjacency Lists)](http://web.ntnu.edu.tw/~algo/Graph.html#4) - 每個點把它的鄰居當成一個串列來存起來。可以使用 C++ STL 中的 vector 來存它的鄰居，因為 vector 是長度可變的陣列。 ```c++ int g[5][5]; // 相鄰矩陣 vector<int> g[5]; // 相鄰串列，vector 裏放相鄰的點 vector<pair<int,int>> g[5] // 以 pair 記錄相鄰的點和邊 ``` - [vector二維陣列(1)](https://ramihaha.tw/c-program-container-vector-array-linklist/)、[(2)](http://f74461036.pixnet.net/blog/post/274951462-c%2b%2b-vector二維陣列) - 補充練習 * [f668. FJCU_109_Winter_Day1_Lab3 Adjacency Matrix 和 Adjacency List 練習](https://zerojudge.tw/ShowProblem?problemid=f668) * (DFS) [c812: 1. 觀光景點](https://zerojudge.tw/ShowProblem?problemid=c812) + 自行練習 p.223-p.224 鄰接矩陣、鄰接串列表示法。 #### 7.2.2. BFS + [圖的搜尋](https://jason-chen-1992.weebly.com/home/-graph-searching-methods) - [深度優先搜尋(Depth First Search, DFS)](https://medium.com/%E7%A8%8B%E5%BC%8F%E4%B9%BE%E8%B2%A8/binarytree-%E5%BB%A3%E5%BA%A6%E6%90%9C%E5%B0%8Bbfs-vs-%E6%B7%B1%E5%BA%A6%E6%90%9C%E5%B0%8Bdfs-ad51a9ca5d68)：以堆疊(Stack)、遞迴來實作。 * DFS 通常寫成遞迴形式，比較好寫，但遞迴的缺點是遞迴的深度會受到限制。 * DFS 與 BFS 一樣可以計算到達的點與無向圖的連通區塊，但是不能算起點到各點的距離。 * DFS 在進階的圖論演算法中有很多重要的應用。 - [廣度優先搜尋(Breadth First Search, BFS)](https://medium.com/%E7%A8%8B%E5%BC%8F%E4%B9%BE%E8%B2%A8/binarytree-%E5%BB%A3%E5%BA%A6%E6%90%9C%E5%B0%8Bbfs-vs-%E6%B7%B1%E5%BA%A6%E6%90%9C%E5%B0%8Bdfs-ad51a9ca5d68)(p.225-p.227)：以佇列(Queue)來實作，BFS通常有下列用途： * 計算某個點出發可以到達的點。 * 在無加權圖中，計算一個點到其他點的距離，或是找兩點的最短路徑。 * 計算無向圖的連通區塊(connected component)。從一個點出發可以拜訪到該點所在的連通區塊的所有點，若對每一個點當起點進行BFS，則可以找到所有連通區塊，但要注意應略過前面的點已經被拜訪過的點。 + BFS 模板(P-7-1) ```c++= vector<int> adj[105]; // 鄰接串列 queue<int> Q; bool visit[105]={false}; // 紀錄點是否已走過，初始為 false int d[105]; // 離起點的最短距離 Q.push(start); visit[start] = true; d[start] = 0; while(!Q.empty()) { int v = Q.front(); Q.pop(); for(int u : adj[v]) { if(!visit[u]) { visit[u] = true; d[u] = d[v] + 1; Q.push(u); } } } ``` + BFS 補充練習 - (裸題) [a982. 迷宮問題#1](https://zerojudge.tw/ShowProblem?problemid=a982) - [f170. m5a1-尋找小狗(Dog)](https://zerojudge.tw/ShowProblem?problemid=f170) - [b059. 4. 靈犬尋寶](https://zerojudge.tw/ShowProblem?problemid=b059) :::info [d090: 例題 P-7-1. 探索距離](https://judge.tcirc.tw/problem/d090) + 在有向圖中從一點 s 做BFS就可以計算可以到達的點，以及 s 到這些點的距離。 + 同時練習鄰接矩陣與鄰接串列的做法。 + 鄰接串列可用 range-based 的寫法：for (int u: adj[v]) ::: :::warning [d093: 習題 P-7-4. 方格棋盤的最少轉彎數路線](https://judge.tcirc.tw/problem/d093) + 把每一次轉彎當作走一步，這是最少步數的問題，所以可以用 BFS 來解。 ::: :::warning [d094: 習題 Q-7-5. 闖關路線 (APCS201910)](https://judge.tcirc.tw/problem/d094) + [解題參考](https://yuihuang.com/tcirc-d094/) ::: #### 7.2.3. DFS + DFS 模板 ```c++= void DFS(int v) { visit[v] = 1; for (int u : adj[v]) { // 使用 C++11 range-based for loop if(!visit[u]) DFS(u); } } ``` + DFS 補充練習 - (裸題) [a290. 新手訓練系列 ~ 圖論](https://zerojudge.tw/ShowProblem?problemid=a290) - (tree) [f673. FJCU_109_Winter_Day2_Lab1 樹高](https://zerojudge.tw/ShowProblem?problemid=f673) - (找環) [b583. 一個環](https://zerojudge.tw/ShowProblem?problemid=b583) - [b554. 5.貪吃龍遊戲](https://zerojudge.tw/ShowProblem?problemid=b554) :::info [d091: 例題 P-7-2. 開車蒐集寶物](https://judge.tcirc.tw/problem/d091) + 輸入一個無向圖，每個點有個權重，要找出最大權重的連通區塊，用 DFS 或 BFS 都可以。 + 同時練習用 DFS、BFS 實作。 ::: :::warning [d092: 例題 P-7-3. 機器人走棋盤 (APCS 201906)](https://judge.tcirc.tw/problem/d092) + DFS ::: :::warning [d100: 習題 Q-7-8. 小寶的著色問題](https://judge.tcirc.tw/problem/d100) + DFS 或 BFS + [二分圖判斷](https://fjuonlinejudge.github.io/Training/graph/bigraph/) 用 color 紀錄每個點的顏色（無色 -1 、紅色 0 、黑色 1 )，一開始每個點紀錄為無色。利用 BFS 或 DFS 遍歷所有點，首先，判斷一個點是否有顏色，如果點為無色，就讓這個點變成紅色，否則照舊。接著，讓其他相鄰且無色的點 v 的顏色和這個顏色相異，並遍歷點 v，如果在遍歷途中發現有任意相鄰點對同色，則該圖不是二分圖。 + 圖可能不連通，每個點都要遍歷。 ::: #### 7.2.4. [DAG 與 topological sort](https://hackmd.io/@bangyewu/Hy2kbYLI6/%2FHnjpQSPXTBSus0IYLOIsSQ?utm_source=preview-mode&utm_medium=rec#DAG-and-Topological-sort) + DAG(directed acyclic graph)指沒有環的有向圖(有向無環圖)，在動態規劃中也用 DAG 來描述狀態轉移。 + 對於一個 DAG，最常找的就是一個拓樸順序(topological sort)，指將所有的點排成一個序列，使得所有的有向邊都是從前往後，而沒有從後往前的邊，拓樸順序顯然不惟一。 + 如何計算一個拓樸順序？常用的方法有兩個。其中一個是利用 DFS，假如在 DFS 時，對每一個點在完成探訪時(return之前)，將該點的編號輸出，那麼將此輸出順序反轉就可以得到一個拓樸順序。證明簡單的說，在執行 DFS(v) 時，所有 v 可以到達的點都是應該排在 v 之後的，而DFS會把這些點都拜訪完畢後才結束 v 的探訪。DFS 的複雜度是線性時間，很多時候不希望使用遞迴，例如 DP 的過程，因為不想(或是環境不允許)使用遞迴，所以才要找拓樸順序，所以需要一個非遞迴的演算法(Kahn演算法)，它的原理就是：只要是in-degree=0的點，也就是沒有箭頭指向它的點，都是可以出列的點。(p.236) + 補充練習 - (裸題) [f167. m4a1-社團 Club](https://zerojudge.tw/ShowProblem?problemid=f167) - [k734. 4. 開啟寶盒](https://zerojudge.tw/ShowProblem?problemid=k734) [題解](https://hackmd.io/@bangyewu/rkL6-NhU2) :::info [d095: 例題 P-7-6. DAG 的最長與最短路徑](https://judge.tcirc.tw/problem/d095) + 假設要計算 DAG G=(V,E,w) 上某點 s 到 t 的最短路徑。對任一點 v，令 d[v] 是 s 到 v 的最短路徑長度，回想在動態規劃時的狀態轉移，可以知道，d[s]=0 而對於 v != s， $d[v]=min\{d[u]+w(u,v): \forall (u,v) \in E\}$ + 其中這些 u 就是 v 的前置狀態。這其實只是一種很簡單的 DP，類似於P-6-6(方格棋盤路線)中從左上走到右下的最大權重路(只能往右往下的棋盤是一個很簡單的DAG)。有了這個遞迴式之後，計算的方向就是 DAG 的拓樸順序，所以只要找到拓樸順序後，計算 d[] 值就可以了；也可以一面找拓樸順序一面計算 d[]。 + 因為邊是有加權長度的，所以在儲存圖的鄰接串列時，需要儲存鄰居的編號以及到達該鄰居的邊長，可採用 adj[u] 中有 {v,w} 表示 u 有一條到 v 的邊，長度為 w。只要跟著拓樸順序來作 DP 就可以了。 + 起點的 in-degree 不一定是 0，而 in-degree 為 0 的點是起點到達不了的(除了起點)，可以把這些點的距離設為無窮大，計算時只計算非無窮大的距離，這樣就可以辨別是否有路徑。 ::: :::warning [d099: 習題 Q-7-7. AOV 最早完工時間](https://judge.tcirc.tw/problem/d099) + 為了進一步識別關鍵工作，需要執行順向遍歷，計算最早開始時間 ES(Earliest Start Time) 和最早完成時間 EF(Earliest Finish Time) 和逆向遍歷，計算最晚開始時間 LS (Latest Start Time) 和最晚完成時間 LF(Latest Finish Time)。如果一個活動的 ES 等於其 LS，則該活動是關鍵工作。 + 程式較長。 ::: ### 7.4. 補充教材(*) #### 7.4.1. Dijkstra演算法 + Dijkstra 為使用貪婪策略(Greedy)的演算法，可以在加權圖上計算一點到所有點的最短路徑。 圖可以是有向或無向，**邊的權重不可以是負的**。 - Dijkstra 每次會選擇「目前」距離起點最近，且尚未確定最短路徑的點。它假設一旦一個點被選中，它的最短路徑就已經被找到並確定了。如果圖中存在負權重邊時，這個假設就不成立了。 - 例如從起點 S 開始，有一條路徑 S→A，權重為 5 為最小。Dijkstra 演算法會先考慮這條路徑，並將 A 的最短距離設為 5。例如果從 S 到 B，權重為 6，而從 B 到 A 的邊權重是 -4。那麼 S→B→A 這條路徑，A 的距離為 6+(−4)=2，比之前算出的 5 還要短。由於 Dijkstra 演算法在處理 A 時，已經假設 5 是最短路徑並將其確定，因此不會再回頭去更新 A 的距離，而錯過這條更短的 S→B→A 路徑。 + 假設輸入的圖是 $G=(V,E,w)$ 與一個起點 $s$，我們要計算 $s$ 到 $V$ 中每一點的一條最短路徑(單源最短路徑)。演算法運作過程中，我們以 $d[v]$ 紀錄目前已知 $s$ 到 $v$ 的最短距離，集合 $Q$ 表示最短距離尚未確定的點，演算法如下： ```c++ // Dijkstra演算法，輸入：G=(V,E,w)與一個起點s 初始化：d[s]=0; 對其他v點，d[v]=oo; Q=V; while 尚有未確定距離的點(Q is not empty) do 在Q中找出d[]最小的點v; 將v移出Q中; // d[v]確定為s到v的最短距離 for each u in adj[v] and in Q do: // 與v相鄰尚未確定距離者 if d[v]+w(v,u) < d[u] then // 從v過來路更近 d[u] = d[v]+w(v,u); parent[u] = v; // 已知到達v之最短路徑的前一點 end if end for end while ``` + [【筆記】Dijkstra algorithm 單點源最短路徑](https://yuihuang.com/dijkstra-algorithm/) + [Dijkstra最短路径算法(波波微课)](https://www.youtube.com/watch?v=8POyTJu-XHw) + [Dijkstra 算法 寻找有权图中最短路 Finding Shortest Path in Weighted Graphs](https://www.youtube.com/watch?v=uyNJxsH16nc) + 補充練習：(裸題) [f628. 2. 村莊與小徑](https://zerojudge.tw/ShowProblem?problemid=f628) :::info [d096: 例題 P-7-9. 最短路徑 (*)](https://judge.tcirc.tw/problem/d096) + 每一回合如何很快地找到 d[] 最小的點，這就需要借助資料結構的幫忙。因為每次找到一點之後，會更新其他點的 d[] ，因此 d[] 是會動態變化的，也就是說無法靠著一開始用排序來處理。可使用 STL priority queue 或 set 實作(set 裏的元素會自動小->大排序)。 ::: **其它最短路徑算法** + [Floyd-Warshall 演算法](https://web.ntnu.edu.tw/~algo/Path3.html)：全點對最短路徑，使用 𝑑𝑝 的觀念，$d_{ij} = min(d_{ij}, \quad d_{ik} + d_{kj})$ - (裸題) [k519. P7.機票 (Ticket)](https://zerojudge.tw/ShowProblem?problemid=k519) - [e792. a3.旅行(Trip)](https://zerojudge.tw/ShowProblem?problemid=e792) - [a674. 10048 - Audiophobia](https://zerojudge.tw/ShowProblem?problemid=a674) + [Bellman-Ford 演算法](https://www.youtube.com/watch?v=YklWOOAR6rs)：單源最短路徑，圖可含有負權重邊，但無負環。時間複雜度比 Dijkstra 演算法高。 - (裸題) [f628. 2. 村莊與小徑](https://zerojudge.tw/ShowProblem?problemid=f628) (NA:96%) #### 7.4.2. (併查集(Union and Find) + 併查集處理的資料是不相交的集合(disjoint set)，如同它的名字，提供的主要操作有兩個：合併兩集合以及查詢某個元素在哪個集合中。可以用來判斷圖中是否有環(加入每一條邊時，兩個端點已經屬於同一集合)、判斷連通性、最小生成榯樹Kruskal演算法。 + [Disjoint Sets 資料結構 : 樹狀儲存](https://web.ntnu.edu.tw/~algo/Set.html#9) + 以人與社團來比喻元素與集合。每一個人都會屬於某個社團，但不會屬於兩個社團。除了社長，每個人 i 都有一個直接領導 parent[i]，社長就是社團的代表人(為了方便，可令 parent[i] = -社團人數)。最簡單的併查集演算法如下： ```c++ find(x): // 給一個人的編號，回傳x所在社團的社長編號 while (parent[x] >= 0) do x = parent[x]; // 一路往上找，直到社長 end while return x; union(x,y): // 合併x與y所在的集合 r1 = find(x); // 找到x的社長老大 r2 = find(y); // 找到y的社長老大 if (r1 != r2) then // 不同社長才要合併 parent[r2] = r1; // 一個社長拜另外一個社長當社長老大 end if ``` + 簡單方法的缺點是，在一連串合併之後，被併的成員會離社長會非常遠，這樣在查找的時候可能會很浪費時間。如何改進？一是每次合併時，把人數少的社團併入人數多的社團。二是**路徑壓縮**：每當要做 find() 的時候，除了找到社長之外，「順便」把尋找過程中碰到的結點的 parent 直接改設成社團社長，讓後續再做查找時，因為路徑都縮短了，就會比較快。優化後的演算法如下： ```c++ find(x): // 回傳x所在集合的代表元素並且做路徑壓縮 (遞迴版) if (parent[x]<0) then return x; end if parent[x] = find(parent[x]); // 遞迴, top-down DP return parent[x]; union(x,y): // 合併x與y所在的集合 r1 = find(x); r2 = find(y); sum = parent[r1] + parent[r2]; // -總人數 if (parent[r1] < parent[r2]) then // 社長的 parent[] 存社團人數的負值，所以大小關係是顛倒的 parent[r2] = r1; parent[r1] = sum; else if (parent[r1] > parent[r2]) then parent[r1] = r2; parent[r2] = sum; end if ``` + 補充練習 - (裸題) [a445. 新手訓練系列- 我的朋友很少](https://zerojudge.tw/ShowProblem?problemid=a445) - (裸題 + 紀錄群體內數量) [f677. FJCU_109_Winter_Day3_Lab1 並查集練習](https://zerojudge.tw/ShowProblem?problemid=f677) :::info [d091: 例題 P-7-2. 開車蒐集寶物](https://judge.tcirc.tw/problem/d091) + 輸入一個無向圖，每個點有個權重，要找出最大權重的連通區塊。 + 練習用併查集實作，每讀到一個邊就把兩端點所在的連通區塊聯集起來。 ::: :::warning [d097: 例題 P-7-10. 挖坑跳 (@@) (TOI 入營考)](https://judge.tcirc.tw/problem/d097) + 一個二維的0/1矩陣，找出連通的1區塊，連通的定義是上下左右四方位。初始找出各個連通區塊可以使用 BFS 或 DFS。題目後半部，有 k 次操作，每次會將某個位置設為 1，如果該位置原來就 1，當然沒事發生，但如果是 0 變成 1，區塊就會變動。這時候如果做 DFS 或 BFS 可能會太花時間，因為最多有 2 萬次操作，每次的區塊可能達到 25 萬點。因為每個點只會屬於某個區塊，使用併查集來維護區塊是好的選擇。 + 二維矩陣每一個格子需要一對 (i,j) 來表示，可以把點 (i,j) 以 row-major 的方式轉成一維陣列的位置 i*(n+2)+j。行數 n 加 2 的原因是外圍多留了一圈當四個邊界，邊界在初值都設成 0 (土堆)。在一維轉換後，每個點的四個鄰居的位移就是 (+1, -1, +n, -n)。 ::: :::warning [d101: 習題 Q-7-11. 紅白彩帶 (APCS201902)](https://judge.tcirc.tw/problem/d101) + 利用 multiset 紀錄每段紅色彩帶的長度，即可快速找出紅色區域最短與最長的長度。 ::: #### 7.4.3. 最小生成樹 + 樹是沒有環路的連通圖，對於一個圖 G，它的一個生成樹(spanning tree)是指挑選 G 的一些邊，將所有點連成一個連通區塊，而挑選的邊形成的是一個樹。因為 n 個點至少要 n-1 個邊才能形成一個連通區塊，而超過 n-1 個邊必然會造成有環路，所以生成樹一定恰好是 n-1 個邊。G 的最小生成樹(minimum spanning tree)是指邊的權重總和最小的生成樹。 + 目前比較常用計算最小生成樹的演算法有兩個：[Prim 演算法與 Kruskal 演算法](https://ithelp.ithome.com.tw/articles/10338718)。 + Prim 演算法與 Dijkstra 演算幾乎一模一樣，屢次找出不在樹上，離樹最近的點。從任選一個點 s 開始，逐步建構我們要的樹 T，每一回合從尚未連進 T 的點中挑選一個點 v 以及一個已經在 T 中的點 u，將 v 與邊 (u,v) 加入 T 中，而挑選的就是一點在 T 中一點不在 T 中的所有邊中，成本最小的邊。重複這個步驟直到全部的點都加入 T 中為止。Prim 演算法與最短路徑的 Dijkstra 演算法只有比大小的 key 值不同，Dijkstra 是起點走過來的總距離，而 Prim 則只看最後與 parent 相連的邊長。實作時與 Dijkstra 一樣使用PQ的技巧，以下為 Prime 演算法： ```c++ // Prim演算法，輸入：G=(V,E,w)與一個任選一個起點s 初始化：T為空，d[s]=0; 對其他v點，d[v]=oo; Q=V; cost=0; // Q是尚未加入T的點, d[v]表示將v加入T的最小成本 while (Q is not empty) do 在Q中找出d[]最小的點v; cost += d[v]; 將v移出Q中; // v加入T中 for each u in adj[v] and in Q do: // 與v相鄰尚未進入T者 if w(v,u) < d[u] then // 從v連過來的成本更小 d[u] = w(v,u); parent[u] = v; // u加入T的最小成本是w(v,u) end if end for end while ``` + Kruskal 演算法為一個使用貪心法(greedy)的演算法。將邊從小到大逐一考慮，一開始為一空樹，如果一個邊加入不會形成環路就把它挑進來；否則將它捨棄。重複挑選邊直到沒有邊或者已經挑到 n-1 個邊為止。如果輸入的是連通圖，最小生成樹一定存在，否則全部的邊都挑完了仍無法形成生成樹。以下為 Kruskal 演算法。 ```c++ // Kruskal演算法，輸入：G=(V,E,w) 初始化：設 T 為空; 初始化一個併查集，每個點自成一個連通區塊; 將所有邊依照權重由小到大排序; for each edge (u,v) do // 依權重由小到大的順序 if u與v不屬於同一個連通區塊 then // find() 將(u,v)加入T中; 將u與v所屬的連通區塊聯集; // union() // 如果T中已經有n-1個邊，可以提早結束 end if end for ``` + 補充練習 - (裸題) [a129. 最小生成樹](https://zerojudge.tw/ShowProblem?problemid=a129) - [e810. 2.潛水 (Diving)](https://zerojudge.tw/ShowProblem?problemid=e810) :::info [d099: 例題 P-7-12. 最小生成樹 (*)](https://judge.tcirc.tw/problem/d098) + 分別以 Prim 與 Dijkstra 演算法實作。 ::: <br/> ## 八、樹上演算法 + 這一章介紹樹(tree)，樹既然是一種圖，圖上的演算法例如 BFS 與 DFS 當然也都能用在樹上。但樹是特別稀疏的圖又有特殊的性質，所以很多問題在樹上有更好的解。另一方面，許多資料結構是使用樹的觀念建構出來的，本章探討的主要是輸入資料是一個樹的問題，而並非用樹做為資料結構的問題。樹上的問題大部分都屬於貪心法則或是動態規劃，但需要搭配樹的結構來處理。 ### 8.1. 基本觀念與名詞 + 自行閱讀 p.267-p.268 ### 8.2. 樹的儲存與基本演算法 #### 8.2.1. 儲存樹的資料結構 + 樹是一種圖，儲存圖的資料結構當然可以用來存樹，但是樹是非常稀疏的圖，所以用鄰接矩陣是非常不合適的。如果是無根樹，用鄰接串列是合適的方式。在有根樹時，還有兩種儲存方式：存 parent 以及存 child(如果 degree 沒有限定，child[] 使用 vector 來做才比較方便，因為陣列長度未知)。 #### 8.2.2. DFS + 樹的 DFS 相當重要，大部分樹的題目都可以用 DFS 來解。 :::info [d102: 例題 P-8-1. 樹上的推銷員](https://judge.tcirc.tw/problem/d102) + 無根樹的DFS。有 n 個城市以 n-1 條道路連接而且每個城市都可以彼此到達，顯示是一個 n 個點 n-1 個邊的連通圖，所以它是個樹。旅行推銷員問題在一般圖上是很難解的問題(d089: 習題 Q-6-25. 貨郎問題 (@@)，[NP-hard](https://lkm543.medium.com/%E6%BC%94%E7%AE%97%E6%B3%95%E4%B8%AD%E7%9A%84-np-%E5%95%8F%E9%A1%8C-db976e55b60b))，但是在樹上卻相當簡單：**最短的環路一定每個邊恰好走兩次**。 + 任何一個 DFS 走的順序都是最短的環路，這一題的問題其實是要找字典順序的 DFS。在做圖的 DFS時，需對每個點需要設定一個 visit[] 值，來避免重複走訪到已經走過的點，但樹的 DFS 可以省略這個動作，因為樹沒有環路。例如從 p 遞迴呼叫到 v，只要不重複走到 p，就不會走到之後的 v。 ::: :::info [d025: 例題 P-8-4. 樹的高度與根 (同P-3-1) (APCS201710)](https://judge.tcirc.tw/problem/d025) + 子節點因數量不定，可用vector諸存 vector<int> child[100000]; + 如果只做純遞迴，時間複雜度會變成 O(nh)，其中 h 是樹的高度。純遞迴的時間複雜度會差，是因為我們沒有把做過的事情用表格記錄下來，如果用 top-down DP 的觀念，使用表格紀錄，即使對每個點呼叫一次，時間複雜度依然只有 O(n)。 ::: :::warning [d106: 例題 P-8-7. 寶石的顏色 (108 全國高中賽)](https://judge.tcirc.tw/problem/d106) + 樹的每個點上有一個顏色，要選擇一個顏色，並且找出一條由根走到某個葉子的路徑，經過所選顏色的點數越多越好。如果只有一種顏色，那就是找一個最長的路徑。 ```c++ // max num of nodes of color col in a path int dfs(int v, int col) { int nc = 0; for (int u: child[v]) { nc = max(nc, dfs(u,col)); } return nc + (c[v]==col); } ``` + 在多種顏色的狀況下，一個簡單的做法是把每一種顏色都算一算，但是時間複雜度會是 O(Cn)，其中 C 是顏色種類數量。例是同樣的路走那麼多次實在不聰明。可以準備一張表格，紀錄目前的路徑上，各種顏色的數量。DFS 過程中，每次走到一點，就將該點顏色數量加一；當 DFS 返回 parent 時，我們可以把該點顏色數減一，以表示回復沒有走到他的狀態。 + 如何找最多顏色呢？如果在表格上找最大值，又需要花 O(C) 的時間。如果聰明一點只在葉節點才計算最大值，可能可以減少一點時間，但是葉節點的數量可能會高達 O(n)，所以還是不好。其實很簡單，在每個節點時，不必去看所有的顏色，因為只有該點的顏色數量有變動，所以只要檢查該點的顏色數量有沒有超過最大值就可以了。 + 最後的問題，顏色的編號並非由 0 或 1 連續編號，而是 10 億以內的非負整數，這表格要如何做呢？其實前面已經學過，就是要做離散化(P-2-2)，離散化可以用 STL map。 ::: #### 8.2.3. BFS + 樹的問題有很多都是 DP 或貪心法則，而都需要一個 top-down 或 bottom-up 的順序，所以通常用 DFS 的比較多，原因是 DFS 比較好寫。在圖的時候，BFS 還有它的必要，例如在無加權圖上求起點到個點距離，這個理由在樹上也不見了，因為樹沒有環路，不管是加權圖或是非加權圖，都可以用 DFS 來計算起點到個點的距離。所以樹上用 BFS 的機會比較少，如果遞迴可用，通常用 DFS，只有因為某些因素遞迴不可用(例如環境限制遞迴深度)，而需要 top-down 順序時才會使用。 :::info [d103: 例題 P-8-2. 物流派送系統](https://judge.tcirc.tw/problem/d103) + 工作站是點，輸送帶是邊，n 個點 n-1 個邊(邊有長度)，而 0 可以到達所有的點，這個圖形就是一個有根樹。第一個要求的是根到各點的最大距離，第二個是經過最多次的邊，那也就是無加權圖的最大距離。 + 在樹上計算根(0)到所有v的距離其實不過就是個簡單的DP，遞迴式 $d[v] = d[parent[v]] + w(parent[v],v)$ for all $v > 0$ + 練習 BFS，因為樹沒有環，樹上找距離也可以用 DFS(遞迴)，程式會更簡潔。 ::: #### 8.2.4. 由下而上的走訪 + 由下而上計算是很多樹的演算法所需要的順序，如果遞迴可以用，通常優先使用DFS；如果不行，就必須自己找一個 bottom-up 順序。非遞迴的找此順序可以採用上一節的BFS，因為將 top-down 順序反轉過來就是 bottom-up 順序。但這樣需要先找順序再做計算，通常要兩回合。 + 有時希望一個回合直接一面找順序一面做計算，其實就是把樹看成一個由下而上的DAG。準備一個queue 放置已經可以出列的點，一開始把所有葉節點都放進 queue，每一回合從 queue 中取出一點，將它的 parent 的孩子數減一，若它的parent變成葉子，就放進queue中。 :::info [d104: 例題 P-8-3. 購物中心選位置](https://judge.tcirc.tw/problem/d104) + 村莊與道路構成的圖顯然是個樹，p(i) 就是 i 的 parent，0 號點是 root。令 D(v) 是點 v 到所有其他點的距離總和，對任一點 v ，可以在 O(n) 的時間計算出 D(v)，所以對每一點 v 都求出 D(v) 來再找最小值的方法可以在 O(n^2^) 完成，因為 n 是1e5，不夠快。 + 假設這些點是在一條數線上，n 個數字要找其中一個與其它數字的距離總和最小，那麼答案是這 n 個數字的中位數(median)，也就是排序後位置在中間的那個數字。如果 n 是偶數，則中間那兩個都是解。 + 在圖上與其它點距離總和最小的點也是稱為 median。樹的 median 與數字的 median 有一樣的性質。若 v 是 D(v) 最小的 v 點，則 v 的每一個分枝的點數都不會超過 n/2。這一題的輸入給的方式是以 0 為 root 的有根樹，因此找 median 其實是要找子樹的點數。令 num(v) 是以點 v 為根的子樹的點數，也就是 v 的後代總數(含 v 自己)，我們要找的是「最低」的某個點 s ，滿足 $num(s)\ge n/2$。最低的意思是，對所有 s 的孩子 c，$num(c)< n/2$。如果 $num(s)$ 恰好是 n/2，則 s 與其 parent 都是 median。根據本題的題意，此時要輸出比較低的那一個 median。 + 若 m 是 median，要算 m 到所有點的距離和，直接的方法當然是把每一條路徑都算出來再加總，其實在樹上有另外一種計算方式。考慮任一條邊 (u,v)，u 是 v 的 parent，邊 (u,v) 把樹分成兩塊，姑且稱為下方與上方，點 m 在 (u,v) 的某一方(如 u 那一邊)，那麼，哪些點到 m 的路徑會經過 (u,v) 呢？當然是 m 另外一方的點(如 v 那一邊)才需要跨過此邊。所以我們只要知道另外一方有幾點，就知道 (u,v) 在距離總和中會被計算多少次，對每個邊都這樣計算後加總就是距離總和了。 + 那麼 m 在哪一方？根據 median 的性質，m 一定在點多的那一方！在計算 num[] 時算出了每一個子樹的大小，所以我們知道 num[v]，不管 m 在上方或下方，這條邊被計算的次數是 $\min(num[v], \ n-num[v])$。有了這個了解，就可以直接算距離總和了。 + 遞迴會更簡潔。 ::: :::warning [d108: 習題 Q-8-6. 樹狀圖的距離總和](https://judge.tcirc.tw/problem/d108) + 計算樹上所有點到所有點的距離。因為 n為1e5，O(n^3^)、O(n^2^) 都不行，需一個 O(n) 的算法，參考 P-8-3 計算median到所有點的距離和的方法。 + 假設 u 的某個子節點 v 連著邊長 len。 設 s[v] 為節點 v 為根的子樹中所含節點數。 N=s.size()-1 為整棵樹的總節點數（扣除索引對齊）。 d[v] 為子樹 v 節點之間，透過 v 計算的所有點對間距之和。 + 進一步希望計算跨越邊 (u,v) 將子樹 v 與其他節點連結所形成的距離貢獻。 對 v 子樹中任一節點 x（ s[v]個 ）與其外節點 y（ N-s[v] 個 ）來說，二者距離必定包含了一段經過邊 (u,v) 的長度，即+len。故距離增加總值為：s[v] * (N - s[v]) * len 這條式放在累計中 d[u] 上，就將「子樹 v 裡每個節點與 v 之外的節點間距增加 len」都累進去了。所以　d[u] += d[v] + s[v] * (N - s[v]) * len; 　　　 u 　　　/　\\ 　　 v　　y 　　/ 　 x ::: ### 8.3. 例題與習題 #### 二元樹 :::info [d105: 例題 P-8-5. 自動分裝 (APCS202002)](https://judge.tcirc.tw/problem/d105) + 二元樹，[題目圖示](https://yuihuang.com/tcirc-d105/)。 + 解這個題目需要會做3件事 1. 儲存此樹狀結構。(二元樹只要存每點的左右孩子編號就可以了) 2. 會計算初始每個中間節點左右的總重量。(DFS) 3. 模擬流程更新重量紀錄。流程描述如下： ```c++ // 進入貨物的重量為x，計算其最後到達的貨箱 v = 1; // 進入點(root)的編號 while v < n: // 尚未到達貨箱 if w[LC[v]] <= w[RC[v]] then v = LC[v] // 左邊較輕往左流 else v = RC[v] // 往右流 end if w[v] = w[v] + x // 更新總重 end while 輸出v // 到達的貨箱編號 ``` ::: #### 樹的最大獨立集 :::info [d107: 例題 P-8-8. 樹的最大獨立集](https://judge.tcirc.tw/problem/d107) + 若 T 是要處理的樹，假設 v 是一個葉。可以宣稱：一定有一個最大獨立集挑選了 v 而沒有挑選parent(v)。證明如下：假設某最大獨立集 S 沒有挑選 v ，那麼一定有挑 parent(v)，可以用 v 點取代 S 中的 parent(v) 得到另外一個獨立集 S’，就是我們宣稱包含 v 的最大獨立集。這樣的替換不可能造成不合法的解，因為 v 點是葉子， parent(v) 是它唯一的鄰居。 + 根據以上的證明，可以得到一個貪心法：對於一棵樹，挑選所有的葉節點，捨棄這些葉節點的parent，重複此步驟直到樹被拔光為止。以題目中的樹為例，我們會先挑{3,4,5,8,7}，捨棄{1,2,6}；然後挑0，結束，所得的獨立集是{0,3,4,5,8,7}，與題目中的解雖然不一樣，但都是最大獨立集。 + 樹的貪心法用 bottom-up 比較自然，只是 bottom-up 的順序需要多一個 queue 來處理。 ::: :::warning [d112: 習題 Q-8-9. 服務中心選位置](https://judge.tcirc.tw/problem/d112) + 我們說一個點可以管轄自己與它的鄰居，「**一個圖上選一些點可以管轄所有的點**」，這樣的集合稱為管轄集(dominating set)，本題要計算樹的最小管轄集。![AP325 Q-8-9(10)](https://hackmd.io/_uploads/H1j3o1-Nle.png =50x) + 對於一般的圖，尋找最小管轄集是一個著名的 NP-hard 問題，沒有已知的多項式時間解法。然而，本題的圖結構是「樹」，這使得我們可以使用更高效的演算法來解決，例如貪心法或動態規劃。 + 以貪心的角度思考，「盡可能地延遲設立服務中心」，只有在萬不得已的情況下，才設立一個服務中心。 + DFS 遍歷以 u 為根的子樹，根據所有子節點 v 回傳的狀態，來決定 u 的決策和狀態。 - 如果有任何一個子節點 v 回傳狀態 0（v 未被覆蓋），那麼 u 必須設立服務中心。此時，我們將服務中心總數 ans 加一，並向 u 的父節點回傳狀態 1。 - 如果沒有任何子節點是狀態 0，但有至少一個子節點 v 回傳狀態 1（v 設立了服務中心），這表示 u 已經被它的子節點 v 覆蓋了。u 不需做任何事，直接向父節點回傳狀態 2。 - 如果所有子節點都不是狀態 0，也不是狀態 1（也就是說，所有子節點都回傳狀態 2），這表示所有子節點都有它們各自的後代來覆蓋，但它們自己都沒有設立服務中心。因此，u 沒有被任何子節點覆蓋。u 只能期望它的父節點來覆蓋它。此時，u 向父節點回傳狀態 0。 - 葉節點沒有子節點，它必定需要父節點來覆蓋，所以直接回傳狀態 0。 + 統整函式返回節點 u 的狀態 回傳值 0: u 未被覆蓋。它需要它的父節點來覆蓋它。 回傳值 1: u 設立了服務中心，因為有某個子節點 v 未被覆蓋，u 必須設立來覆蓋 v。 回傳值 2: u 沒有設立服務中心，但被它的某個有服務中心的子節點所覆蓋。 ::: :::warning [d113: 習題 Q-8-10. 竊聽間諜網](https://judge.tcirc.tw/problem/d113) + 一個點可以cover它所接的邊，「**在一個圖中選一些點cover所有的邊**」，這樣的點集合稱為vertex cover，也就是每一個邊的兩端點都至少被選中一點，本題是樹的無權重的最小頂點覆蓋(minimum vertex cover)。![AP325 Q-8-9(10) (1)](https://hackmd.io/_uploads/SJr131ZNee.png =50x) + 對於一般圖，求最小頂點覆蓋是 NP-hard 問題。但本題的結構是樹，我們可以用高效的貪心演算法來解決。貪心的策略是「盡量不放竊聽器，直到不得不放為止」，從樹的葉子節點開始，由下而上地進行決策。 + DFS 遍歷以 u 為根的子樹，根據所有子節點 v 回傳的狀態，來決定 u 的決策和狀態。 - 如果 u 的所有孩子都回傳了狀態 1（它們自己都安裝了），那麼 u 就沒有必要再安裝了，讓 u 回傳狀態 0 (表示 u 沒有安裝)。 - 如果任何一個孩子 v 回傳了狀態 0（v 沒有安裝竊聽器），表示 (u, v) 這條邊還沒有被覆蓋。為了覆蓋它，必須在 u 身上安裝竊聽器。只要有任何一個孩子需要 u 來覆蓋，就將竊聽器總數加一，並讓 u 回傳狀態 1（表示 u 已安裝）。 ::: :::warning [d109: 例題 P-8-11. 公司派對 (NCPC)](https://judge.tcirc.tw/problem/d109) + P-8-8 的加權版，最大權重獨立集。 + 無加權時要挑選最多不相鄰的點，加權時要挑選總和最大的不相鄰的點。無加權時，貪心法則可以找到最多的點，但是在有加權時，貪心的方法並無法找到最加解，嘗試用 DP 的觀點來找答案。 + 對任一點 v，令 f(v) 代表以 v 為根的子樹的最佳解，也就是在 v 的後代(含 v )中，不相鄰的點最大可能的權重和，但在寫狀態轉移式時候遇到困難，因為 v 點是否有選會影響他的孩子是否可以挑選。碰到類似狀況時，把解分類是通常的解決方法。 + 把解分成兩類，狀態定義： 1.f~0~(v) 是以 v 為根的子樹中，不挑選 v 的狀態下之最佳解。 2.f~1~(v) 是以 v 為根的子樹中，挑選 v 的狀態下之最佳解。 + 狀態轉移方程： $f_0(v) = \sum_{u \in child(v)} \max\{f_0(u),f_1(u)\}$ // 當 v 不選時，他的孩子可挑，可不挑 $f_1(v) = r(v) + \sum_{u\in child(v)} f_0(u)$ // 當 v 被挑選時，他的孩子都不可以挑 最後的答案在 $\max\{f_0(r), f_1(r)\}$，其中 r 是根。 + 回顧在第六章的P-6-2(不連續的表演酬勞)，其實那就是一個一維陣列的最大獨立集問題，而一維陣列是樹的一種特殊形式，所以也可以仿效 P-6-2 的解法來想這一題的 DP。只設一個遞迴函數 f(v) 是 v 子樹的最佳解，v 不挑時，選各子樹的解相加；而 v 挑選時，將 v 的孫子(孩子的孩子)為根的子樹的解拿來相加。因為一個點只有一個祖父，這樣做的複雜度還是O(n)。 ::: #### Tree DP + 樹是 DP 的完美應用場景，因為它滿足 DP 所需的幾個核心條件： - 類似 DAG 的無環特性：樹沒有環，任意兩點之間只有一條唯一路徑。這使得 DP 狀態轉移可以沿著明確的父子關係進行，有效避免循環計算的問題。 - 遞迴特性：樹的結構具有天然的遞迴性，一個節點的解通常可以透過其子節點的解來遞迴定義，符合 DP 的狀態轉移思想。 - 獨立子問題：各子樹之間是完全獨立且互不相交的。這允許我們將每個子樹的問題視為獨立子問題來解決，並將其結果組合起來，從而避免重複計算。 - 許多在一般圖上難以直接應用的 DP 演算法，在樹上可以藉由 DFS 搭配狀態轉移，高效地求得解。 :::info [d114: 習題 Q-8-12. 佔領連續的城鎮](https://judge.tcirc.tw/problem/d114) + 找到樹中一個權重總和最大的相連子圖，類似 P-4-13最大連續子陣列 (Maximum Subarray)。 + 狀態定義：dp[u] 為在以 u 為根的子樹中(包含 u)，相連子圖能夠獲得的最大利益。 + 狀態轉移方程：$dp[u] = w[u] + \sum_{v \in \text{children}(u)} \max(0, dp[v])$ + 總和利益就是 dp[u] 中的最大值：$\text{ans} = \max \left( 0, \max_{u=1}^{n} (dp[u]) \right)$ ::: :::warning [d110: 例題 P-8-13. 不同成本的購物中心 (@@)](https://judge.tcirc.tw/problem/d110) + 這一題是Q-8-9 服務中心選位置的加權版本，要計算 minimum weight domination set，與最大獨立集類似的地方是：無加權時可以貪心，加權時必須用DP來解。 + 最大獨立集的 DP 遞迴式比較容易，這一題的困難點並不是程式難寫或是需要什麼特別的資料結構與演算法，而是DP遞迴式很容易弄錯，狀態定義分成三類： - $d1(r)$: 在 $r$ 被挑選下的最佳解(domination set的最小權重)。 - $d01(r)$: 在 $r$ 不被挑選但 $r$ 已被管轄下的最佳解，也就是至少有一個 $r$ 的孩子被挑選。 - $d00(r)$: 在 $r$ 不被挑選且 $r$ 不一定有沒有被管轄之下的最佳解。這個值未必是個合法的解，$r$ 要靠上面的點管轄。 + 狀態轉移方程：($v$ 為 $r$ 的孩子)： - $d1(r) = w(r) + \sum_{v\in child(r)} \min\{d00(v),d1(v)\}$。也就是對所有子樹的最小值加總後加上r的權重，因為 $d00(v)\le d01(v)$，所以只需要取$\min\{d00(v),d1(v)\}$。 - $d00(r) = \sum_{v\in child(r)} \min\{d1(v),d01(v)\}$ - $d01(r) = \sum_{v\in child(r)}\min\{d1(v),d01(v)\} + min\_diff$ ，其中 $min\_diff = \max\{0, \min_{v\in child(r)}\{d1(v)-d01(v)\}\}$，也就是對所有孩子$v$找出$d1(v)-d01(v)$的最小值，這個值是正的就要加上，如果是負的就不加。遞迴式的意義在各孩子的最小合法解之總和，但是不能全部的孩子都沒有挑選。 ::: #### 樹直徑 :::info [d111: 例題 P-8-14. 血緣關係 (APCS201603)](https://judge.tcirc.tw/problem/d111)([圖示](https://zerojudge.tw/ShowProblem?problemid=b967)) + 在一個圖中，最長的兩點最短路徑(距離)稱為直徑。如果對任意兩點 u, v 都求出兩點之間的最短距離 d(u, v)，那麼 $diameter = \max\{d(u,v): \forall u,v \in V\}$。在前面的題目中已經知道，樹上求一點與其它點的距離可以在 O(n) 時間內完成，那麼直接依照定義求出所有點到所有點的距離然後計算直徑可以在 O(n^2^) 時間完成，需要一個更有效率的解法。 + 因為直徑必然由某個葉節點往上走到某個點 r 之後，再從 r 的另外一個孩子一路往下走，退化的狀態是 r 只有一個孩子，那就只走到 r 為止，我們稱這樣的路徑為以 r 為最高點的路徑。只要對每個 r，計算出以 r 為最高點往下的兩條最長路徑(這兩條路徑必須經由兩個不同的孩子)，然後對所有的 r 取最大值就可以了。前面 P-8-4 學過樹中點的高度，我們要找的就是 r 的兩個高度最高的孩子，把他們的高度相加再＋2，就是以 r 為最高點的最長路徑。 + 以 top-down 寫法的主架構當然還是 DFS，在對所有孩子遞迴呼叫後，任務是找出深度最高的兩個孩子(就像在一個數列中找出最大的兩個值一樣)。 - 最直接的寫法需要用兩次迴圈，第一次找出最大值，第二次找出非最大值中的最大值。 - 或者掃描一次但同時維護好第一名與第二名。 - 有沒有更簡單的寫法？假設數列是 S，pm 是 prefix_max，則最大兩個元素之和其實就是 max(S[i]+pm(i): for all i)。所以只需要一路掃描並維護好目前看到的最大值，每次將當下看到的值加上他之前的最大值相加即可。 + 樹的直徑還有另外一個演算法，根據圖論的一個性質：「距離樹上**任一點**最遠的點，一定是某個直徑的端點」。根據上述的性質，可以得到一個很簡單的線性時間演算法，稱為 farthest of farthest 演算法：挑選任一點 v ，找離它最遠的一點 u ，再找離 u 最遠的一點 s ，則 u 到 s 就是直徑。([證明](https://hackmd.io/@aacp/tree_diameter_dfs_2times)) + 同時練習 farthest of farthest 的作法。 ::: :::warning [d115: 習題 Q-8-15. 樹上一位不回家的推銷員](https://judge.tcirc.tw/problem/d115) + P-8-1 的加權版。給定一棵樹（n - 1 條邊連通 n 個城市），想走訪所有節點至少一次，不必返回起點。 + 要訪問所有城市，如果要回到原點，最有效率的方法是走遍所有的邊。如果每一條邊都走兩次（來回），那麼總路徑長度就是所有邊權重總和的兩倍。 + 然而推銷員可以從任何城市開始，也可以在任何城市結束。為了最小化路徑長度，應該充份利用這點。想像如果你有一條路徑，你可以選擇不走回頭路的部分，那麼這個「不回頭路」的部分應該要儘可能的長，這樣就能最大化地減少總距離。這條最長的路徑就是樹直徑。 + 因此最短的旅行距離=(∑所有邊的權重)×2−樹直徑 + 練習farthest-of-farthest（兩次 DFS/BFS） 找樹直徑的方法 - 第一次從任意節點出發（如 0），找到最遠節點 u。 - 第二次從 u 出發，找到距離最深且距離為 diameter 的 s。 :::