New Thread
#43503: 動態規劃五步法


chiuliyou@gmail.com (邱立宇)

School : 新北市立永平高級中學
ID : 136609
IP address : [106.1.117.161]
Last Login ：
2024-10-26 13:36:59
d890. 3.禮物分配(gift) -- 99學年度台北市資訊學科能力競賽 | From: [106.1.117.161] | Post Date : 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