演算法高階・進階動態規劃
樹上的挑或不挑、最長共同子序列並照規則還原、相鄰合併的區間動態規劃。
這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。
- 01
樹狀叢集挑節點做抽檢
困難樹狀動態規劃叢集的網路是一棵樹:節點 1 是核心交換器,其他每個節點都接在一個父節點下面。要挑一些節點跑抽樣檢測,每個節點跑完有一個效益分數(可能是負的,表示成本大於效益)。同一條上行鏈路不能同時有兩端在檢測,所以父子節點不能同時被挑。可以一個都不挑。請算出效益總和的最大值。
輸入:
第 1 行:組數 t
接下來 t 行:每行一棵樹,格式是
v1 v2 … vn ; p2 p3 … pn:分號前是節點 1 到 n 的效益分數,分號後是節點 2 到 n 的父節點編號(n = 1 時分號後是空的)。保證每個節點的父節點編號比它自己小。也可能是
GEN n seed lo hi span:由 starter 的gen_tree產生 n 個節點,效益在 lo 到 hi 之間,節點 i 的父節點落在 i−span 到 i−1 之間(span = 1 時整棵樹是一條鏈)。GEN開頭的行是大量測資的縮寫:starter 已寫好產生資料的函式,讀進來後跟一般的資料一樣,不用自己處理。輸出:每棵樹一行,效益總和的最大值。
要求:每個節點算兩個值:「挑這個節點時,它的子樹最多拿多少」與「不挑它時最多拿多少」。樹可能深達幾千層,遞迴會超過 Python 的預設深度上限;利用「父節點編號比較小」,由編號大到小處理節點,就能保證處理父節點前所有子節點都算好了。
範例輸入:
2
2 9 4 ; 1 1
6 2 2 8 ; 1 2 3
範例輸出:
13
14
類型對應:LeetCode「House Robber III」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 02
管線版本差異的共同步驟
困難動態規劃管線改版時,要比對新舊兩版的步驟序列:找出兩版都有、而且先後順序一致的最長步驟序列(最長共同子序列,不必連續),其他步驟就是被移除或新增的。
最長共同子序列可能不只一條,請照下面的規則還原出唯一的一條。令
f[i][j]是「舊版從第 i 個步驟起(a[i:])」與「新版從第 j 個步驟起(b[j:])」的最長共同子序列長度(索引從 0 起算)。從 i = 0、j = 0 開始,重複到任一邊走完:a[i] == b[j]:把這個步驟放進結果,i、j 都加 1- 否則
f[i+1][j] >= f[i][j+1]時 i 加 1,不然 j 加 1
輸入:
第 1 行:組數 t
每組 2 行:第 1 行是舊版、第 2 行是新版,各是一串步驟名稱(以空白分隔,至少一個),或
GEN n seed k(由 starter 產生 n 個步驟,名稱是s1到sk)。GEN開頭的行是大量測資的縮寫:starter 已寫好產生資料的函式,讀進來後跟一般的資料一樣,不用自己處理。輸出:每組三行
LCS 長度- 還原出的步驟,以空白分隔;長度是 0 時印
NONE removed 舊版不在結果中的步驟數 added 新版不在結果中的步驟數
要求:用 (n+1)×(m+1) 的表從後往前填
f,再照規則從前往後還原;不要列舉子序列。範例輸入:
2
read parse write
read write log
a b c
c b a
範例輸出:
LCS 2
read write
removed 1 added 1
LCS 1
c
removed 2 added 2
類型對應:LeetCode「Longest Common Subsequence」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 03
合併相鄰小檔的最低成本
困難區間動態規劃資料湖的某個分區累積了一排依時間排序的小檔案,大小分別是 s1, s2, …, sn(MB)。壓實(compaction)程式每次只能把「相鄰」的兩個檔案合併成一個,合併的成本是兩個檔案大小的和,新檔案留在原本的位置(時間順序不能亂)。重複合併直到只剩一個檔案。請算出總成本的最小值,並說明最後一次合併是在哪裡切開。
最後一次合併會把「第 1 到第 k 個原始檔案合成的檔」與「第 k+1 到第 n 個原始檔案合成的檔」合起來,k 稱為切點。總成本最小的做法可能不只一種,切點取所有最佳做法中最小的 k。
輸入:
第 1 行:組數 t
接下來 t 行:每行一組檔案大小(正整數,以空白分隔,至少一個),或
GEN n seed lo hi。GEN開頭的行是大量測資的縮寫:starter 已寫好產生資料的函式,讀進來後跟一般的資料一樣,不用自己處理。輸出:每組一行
最小總成本 切點;只有一個檔案時不用合併,印0 -。要求:用區間動態規劃:
dp[i][j]是把第 i 到第 j 個檔案合成一個的最小成本,由短區間往長區間填,O(n³)。注意這跟「每次挑最小的兩個合併」不同:只能合併相鄰的。範例輸入:
2
3 1 2
7 7 7
範例輸出:
9 1
35 1
類型對應:LeetCode「Minimum Cost to Merge Stones」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答

送件鴿飛出去了