2017/10/06の精進

ACするたびに記録をつけていって一日の終わりに投稿しようかな(これを書いているのは朝)

さて、今日は木DPをやる

・ABC 036 塗り絵

dp[v][i]=頂点vを色i(0:白 1:黒)で塗るとき、subtree(v)の塗り方は何通りか

・yukicoder No.417 チューリップバブル

最終的に頂点0に戻らなくてはいけないので、通る辺は必ず往復する よってコストを2倍しておいて戻ることをかんがえないことにする

dp[v][i]=のこり時間がiのときsubtree(v)で得られる税収の最大値

という木DPをするのはわかるが更新がわからなかった

vの子uについて、vからuに行くのにコストがcかかり、subtree(u)で時間をj使うとするとdp[v][i]=max(dp[v][i],dp[v][i-(j+c)]+dp[u][j])となる

同じ子を何回も辿らないためにはiを大きい方から回せばいい(再利用DPと同じ理屈)

明日続きをやります