Bit DPと再帰関数

Quiz

• No.771 しおり
• https://yukicoder.me/problems/no/771

AC

• https://yukicoder.me/submissions/353958

他の人の解説記事

• はまやんはまやんさん
  • https://www.hamayanhamayan.com/entry/2019/01/02/214632

解法

• 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)も同様