作者sophialiege ()
看板ACMCLUB
标题Re: 问一下昨天的problem J
时间Sun Oct 16 15:32:47 2005
※ 引述《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