典型タグ

繰り上がり・混合基数DP

整除鎖の丸め、支払いと釣銭、複数項の加算を下位桁から処理し、次の桁へ渡すcarry・borrowだけを状態に保つ。

この典型を扱う単元: 繰り上がり・借り・混合基数を状態にするDP

検索別名: carry DP、mixed-radix DP、混合基数DP、繰り上がりDP

未知問からこの典型を見つける手掛かり

扱う対象
  • borrow
  • carry
  • 整除鎖
  • 桁
  • 混合基数
  • 額面
使う手掛かり
  • 下位桁から
  • 切り上げ
  • 切り下げ
  • 繰り上がり
  • 釣銭
保つ不変量
  • 整除関係
  • 有限carry vector
  • 次桁へのcarry
  • 端数
求めるもの
  • 加算制約
  • 可解性
  • 最小枚数
  • 解数
適用しない条件
  • tight
  • 文字列automaton
  • 未満フラグ
分類・前提・学習成果

分類と直接の前提

概念上の親: DP状態と遷移

関連する典型

  • 上限制約付き桁DP: 上限との接頭辞一致を保つ桁DPと、下位桁から繰り上がりだけを渡す混合基数DPを区別する。

学習成果と学習単位

代表問題

この典型の考え方を具体的な問題で確かめるための入口です。

関連問題

この典型が主タグまたは補助タグとして付いている問題です。