7K12 blog

猫でも分かるアルゴリズム解説

ABC142 E - Get Everything

f:id:tkr987:20200524182335p:plain

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];

f:id:tkr987:20200524182607p:plain

制約からbitDPと分かる。

各鍵key[i]と宝箱の空き状態をbitで表現し dp[state] := 宝箱の空き状態がstateとなる最善費用 とする。bitで表現した宝箱の空き状態  j = [00...0]から[11...1] 組み合わせ全てに対して以下の更新を試すと答えが得られる。計算量は O(2^NM)

next = j | key[i];

dp[next] = min( dp[next], dp[j] + a[i] );

 

EDPC-O が類題になる

https://atcoder.jp/contests/dp/tasks/dp_o