https://atcoder.jp/contests/abc142/submissions/11902212
- 初期値はdp[0]=0
- 繰り返しは rep(i, 0, M) rep(j, 0, Pow2(N))
- 遷移は dp[next] = min(dp[next], dp[j] + key[i].a);
- 出力は dp[Pow2(N) - 1];
制約からbitDPと分かる。
各鍵key[i]と宝箱の空き状態をbitで表現し dp[state] := 宝箱の空き状態がstateとなる最善費用 とする。bitで表現した宝箱の空き状態 j = [00...0]から[11...1] 組み合わせ全てに対して以下の更新を試すと答えが得られる。計算量は
next = j | key[i];
dp[next] = min( dp[next], dp[j] + a[i] );
EDPC-O が類題になる
