演算法中階・動態規劃入門
從前一步推下一步:不選相鄰、最大連續區段、切批方法數。
這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。
- 01
相鄰節點不同時下線
中等動態規劃機房的一排節點要挑幾台今晚下線,清掉暫存檔回收磁碟空間。每台可回收的 GB 數已知。為了維持冗餘,相鄰的兩台不能同時下線。請算出最多能回收多少 GB。
輸入:
第 1 行:組數 t
接下來 t 行:每行是一排節點由左到右的可回收 GB 數(非負整數,以空白分隔,至少一台)
輸出:每組一行,最多可回收的 GB 數。
要求:用動態規劃,一次走完、只留兩個變數;不要列舉所有選法(n 台有 2^n 種選法)。
範例輸入:
2
3 10 4 6
8 1
範例輸出:
16
8
類型對應:LeetCode「House Robber」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 02
淨流入最大的連續區段
中等動態規劃一個資料湖每天的淨新增容量(GB,新增減去清除,可能是負數)記錄成一串整數。容量規劃要找出「連續幾天的淨新增總和最大」的那一段。
輸入:
第 1 行:組數 t
接下來 t 行:每行是一段期間每天的淨新增(整數,以空白分隔,至少一天,第一筆是第 1 天)
輸出:每組一行
總和 起始日 結束日(日從 1 起算,區段至少一天)。總和最大的區段有好幾段時,取起始日最早的;起始日也一樣時取最短的。要求:一次走完(O(n)),不要對每個起點往後加總。
範例輸入:
2
4 -6 3 5 -2 4
-5 -2 -8
範例輸出:
10 3 6
-2 2 2
類型對應:LeetCode「Maximum Subarray」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 03
資料切批的方法數
中等動態規劃一份 n 筆的資料要依序切成好幾批送出,每一批的筆數只能是允許清單裡的值。只要切出來的批次大小序列不同就算不同的切法(例如 n=3、允許 1 和 2 時,1+2、2+1、1+1+1 是 3 種)。這就是「爬樓梯一次可以爬幾階」的推廣。
輸入:
第 1 行:組數 t
接下來 t 行:每行第一個數是 n(1 ≤ n ≤ 500),後面是允許的批次大小(正整數,以空白分隔,彼此不重複)
輸出:每組一行,切法的數量除以 1000000007 的餘數;切不出來印
0。要求:用動態規劃由小到大算 ways[0..n],不要用遞迴列舉每一種切法。
範例輸入:
2
4 1 2
5 2 4
範例輸出:
5
0
類型對應:LeetCode「Combination Sum IV」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答

送件鴿飛出去了