挿入 DP の二つの型について - りきぽん's 競プロblog

割り込み型

• 割り込みの例
  • 長さ5の数列に1つ新しい値を挿入する方法は6通り
    • $(n+1)! = (n+1) n!$ というノリ
  • 長さ5の数列に同じ値を3つ挿入する方法は $\binom{5+3}{3}$ 通り
    • $\displaystyle \frac{(a+b+c)!}{a!\ b!\ c!} = \binom{a}{a}\binom{a+b}{b} \binom{a+b+c}{c}$ というノリ
• 問題例
  • エクサウィザーズ2019 D - Modulo Operations
• ABC358 F - Alphabet Tiles

メモ

• 挿入ソートと関係ありそう。
  • 挿入ソートを知っていると挿入DPも自然に見えそう。
• 最適化問題で挿入DPすることはある？bitDPとの違いは？