URL
https://community.topcoder.com/stat?c=problem_statement&pm=14811
概略
有向木の頂点に石を置いていくゲームを行う．葉には無条件で置いてよい．親に置くためには，その直接の子すべてに石が置かれていなければならない．また，任意のタイミングで石を取り除くことができる．根に石を置いた時点でゲームは終了する．
各頂点には重み $w$ が付いている．石が置かれている頂点 $i$ について $W = \sum w_i$ が逐一計算され，ゲームのスコアは $\max W$ である．スコアの最小値を求める．
方針
操作を先読みしたいときにはメモ化再帰が有効です．
dp[i] := iに石を置く操作をするときのスコアの最小値とします．頂点iの子がL，Rであるとき，iに石を置く操作には以下の工程が考えられます．
Lに石を置くdp[L]
Rに石を置くdp[R]
Lに石を置く操作を一通り行った後，Rに置く操作を行う．またはその逆．これは小さい方を選択できる．min(w[L] + dp[R], w[R] + dp[L])
LとRの両方に石が置かれていて，iに石を置くw[i] + w[L] + w[R]
dp[i]はこのうちの最大値を取ります．子が0, 1つの場合も同様に計算できます．
[展開する]
反省
操作順を親と子の重みだけで評価できると思って時間を溶かす．そんなわけない．
Tweet comments powered by Disqus