高中生程式解題系統

#43503: 動態規劃五步法

學校: 新北市立永平高級中學

編號: 136609

來源: [61.228.158.165]

註冊時間:

2020-10-21 14:11:45

最後登入時間:

2024-10-26 13:36:59

d890. 3.禮物分配(gift) -- 99學年度台北市資訊學科能力競賽 | From: [106.1.117.161] | 發表日期: 2024-10-20 23:16

1. 構造問題: 把禮物盡量平均分配

2. 定義狀態: f(價格) = 能不能湊出來

3. 求解小規模的簡單問題:

f(0) = true

f(sum) = true

4. 狀態轉移方程式:

若 f(i) = true, f(i + num) = true

反過來說 f(i) = true, f(i - num) = true

5. 判斷複雜度: O(n * sum / 2)

ZeroJudge Forum