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

POJ 3493 Chessboard Puzzle

題目是說, 給出一個 n*n 的 grid, 每格有一個分數 (可以負), 現在要將每格染成白色或黑色, 總分計算的方法是:
----如果兩格相鄰而且異色, 把它們分數的乘積加到總分
問最大可能總分, n <= 16

---

做法是使用狀態DP
一開始是想用像炮兵陣地的方法DP, 即state是記一行的permutation, 但單是做一次transfer便要2²ⁿ了

後來聽超超說,
有一個很強的加速

考慮到每一格是黑/白最「遠」也只是影響到下面那格 (假設順序是一行行由左至右)
即 n 格後
可以順著做而且只記著前n步的狀態

即

......
......
......
......
......
......

做到紅色那格時, 只用記著藍色的排列, 每次transfer後只是把排列shift後一格 ->

......
......
......
......
......
......

把time complexity降至O(n²*2ⁿ)