ABC142 E - Get Everything - ツバサの備忘録

解法

制約がbitDPをしろと言っているので、bitDPをします。
$dp[S] =$ 現在開けた宝箱の状態が $S$ のときに、そこからかかる費用の最小値
とします。
$S$ を整数型の変数1つで表し、2進数の桁に宝を割り振り、0:まだ開いていない、1:開いている、とすると
初期値は $dp[2^{N}-1] = 0$ で、答えは $dp[0]$ です。
$dp[S]$ を求めることについて考えると、
状態が $S$ の際に $i$ 番目の鍵を使うと、 $S \cup T_{i}$ (ただし、 $T_{i}$ は $i$ 番目の鍵を使用して開けることのできる宝箱の集合)
となります。
鍵は $M$ 種類あり、これを全部試せばよく、
$dp[S] = min(dp[S \cup T_{i} ] +a_{i})$
となります。 $S \cup T_{i} = S$ のパターンは注意する必要があり、スルーしなければなりません。
あとはこれを繰り返せば答えが求まります。
$O(2^{N}MN)$ なのですが、 $T_{i}$ を前計算してあげると $O(2^{N}M)$ になります(自分は前計算してないです)

感想

久々にbitDPを見た気がします…
やっぱりbitDPに関しては再帰で書くのが個人的には好きです