AI & Data Dreamers練功房
寶箱片場規則
ALGO GATES・演算法關卡・中階・3 題

演算法中階・動態規劃入門

從前一步推下一步:不選相鄰、最大連續區段、切批方法數。

這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。

  1. 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 執行,只用標準函式庫。

    作答登入後可作答
  2. 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 執行,只用標準函式庫。

    作答登入後可作答
  3. 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 執行,只用標準函式庫。

    作答登入後可作答