POJ 2152 Fire

Problem statement

Given a undirected tree, each vertex can be selected or not. The cost is defined as:

If vertex x is selected, cost = prize[x]

If vertex x is not selected, cost = distance to the nearest selected vertex

In addition, for each vertex x, the distance to the nearest selected vertex must <= distance[x]
Find the minimum cost, |V| <= 1000

Solution

其實都幾 obvious 係 dp on tree
不過個 state 比較難諗

dp[x][y] = minimum cost for subtree rooted at x, with the nearest vertex is y

就係個 state
進行 state transfer 時, 主要分的 case 為
1. y 在 x 的 subtree
2. y 不在 x 的 subtree
(畫下就可以推到)

time complexity = O(N²)

類似方法應該可以解決 Hsinchu 2009 的 D