Bit DPと再帰関数

Quiz

https://yukicoder.me/problems/no/771

AC Code

https://yukicoder.me/submissions/353958

他の人の解説記事

解法

  • Bit DP
  • 蟻本(v2)で言うと、p173の巡回セールスマン問題
  • そこに書かれているように、表を埋める順番がイメージしづらい時はメモ化再帰で書くといい

DPテーブル定義

  • はまやんはまやんさんと同様に
    • dp[msk][lst] := 今までmskの本が本棚に入っていて、最後の本がlstのときの醜さ

メモ化再帰

  • 本をすべて置き終わった状態から過去にさかのぼっていく
rec(mask, i)
第1引数:2進数表現
第2引数:最後においた本のindex

rec(111, 0)
  rec(110, 1)
    rec(100, 2) => 0
  rec(110, 2)
    rec(010, 1) => 0

rec(111, 1), rec(111, 2)も同様