Educational DP Contest:P - Independent Set
問題
解法
dp(i, f) := 頂点 i を黒で塗れるかどうかが f のとき,頂点 i から到達できる頂点を塗り分ける通り数
と定義する.このとき,
dp(i, f) = dp(v_1, true) * dp(v_2, true) * ... (f == false のとき)
dp(i, f) = dp(v_1, false) * dp(v_2, false) * ... + dp(v_1, true) * dp(v_2, true) * ... (f == true のとき)
(v は頂点 i から直接行ける頂点)
と漸化式が立つ.状態数 O(N),遷移 O(N) だけれども,各辺は1回しか見ないので O(N + N).
解答
実装に関して,無限ループを避けるため,親の頂点を dp の引数に持ちながら dp すればよい.