※ 引述《sophialiege ()》之銘言：
: ※ 引述《sophialiege ()》之銘言：
: : 題目: 給定一個 undirected tree T, T 每個 node 有兩個 attribute [a,w]
: : a是整數,w是正整數
: : 另給兩個正整數Wmin和Wmax 1<= Wmin, Wmax <=10000
: : 要求: 找出一個T的subtree T',使得 floor(T'內的a總合/T'內的w總合) 要最大
: : 且T'內的w總和要 >=Wmin <=Wmax
: 我的想法是先隨意pick一個node當root
: 考慮optimal solution包不包含root的情況
: 不包含就變成更小的問題,因為被root斷開的任意兩subset不可能不經root而形成tree
: 包含就有點像list的方法解下去 <= 這一步不太清楚要怎麼做
我想出來了,這裡用DP就可以做出來了
一樣把問題變成更小的subset(由root斷開),subset的return result是
i belongs to [1..10000]的對應 max floor(..../(i))
複雜度要 (Wmax-Wmin)*|E|
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.250.175