問題概要

鍵がたくさんあり、それぞれに値段と開けられる宝箱が決まっているので、全ての宝箱を開けられる鍵の組み合わせの内で値段総和の最小を答える問題です。

考え方

宝箱の個数が $\leq 12$ なので、宝箱の集合はbitで表現できます。

ただ、選ぶのは鍵なので宝箱を全探索は出来ません。

ここでbit全探索という選択は無くなりますが、bitを使う前提で他の手段を考えるとbit DPが思い当たります。

鍵を選ぶか選ばないかは何とかするとして、開けられる宝箱の一覧を添字で管理できるのではないかと考えられます。

そして、これは選ぶか選ばないかのDPでよくありますが、$i$ 番目までの要素に対する何らかの計算結果が $j$ = $v$ で表せる時、配列を $dp[i][j] = v$ となるように作ることで

$dp[i + 1][j] += dp[i][j]$

$dp[i + 1][j$ に何かの計算を行う $] += dp[i][j]$

または、これらに準ずる漸化式

で $Ο(n \max{j})$ ($n$ は全ての要素数) 程度の計算量で解ける場合が非常に多いです。

今回はbitで宝箱の集合を管理するので、$i$ が鍵で $j$ が宝箱の集合とすると

$dp[i+1][j] = \min(dp[i+1][j], dp[i][j])$

$dp[i+1][j \lor $ 鍵 $i$ が開けられる宝箱の集合 $] = \min($ 左辺 $, dp[i][j] + $ 鍵 $i$ の価格 $)$ (ここで、$\lor$ はbitwise or)

という漸化式を立ててループを回すことでこの問題を解けます。

ここで初期条件は $dp[0][0] = 0$ でそれ以外は $10^9$ とかにしておけばよいです。価格の総和はどう頑張っても $M \cdot \max{a}$ (厳密にはもっと少ない)となります。

また、dp配列の大きさは $(m + 1, $ 1<<n $)$ であり、ループ終了後答えがあるのは $dp[m][$ (1<<n)-1 $]$ (0-indexed)です。

計算量は特に工夫しなくても余裕ですが、先にそれぞれの鍵について開けられる宝箱の集合をbit値にしてしまえばbitwise orを掛けるだけになって高速になります。

そのような処理をすれば $Ο(2^NM)$

そうでなくとも $Ο(2^NNM)$ を達成します。