繰り上がり・混合基数DP
整除鎖の丸め、支払いと釣銭、複数項の加算を下位桁から処理し、次の桁へ渡すcarry・borrowだけを状態に保つ。
この典型を扱う単元: 繰り上がり・借り・混合基数を状態にするDP
検索別名: carry DP、mixed-radix DP、混合基数DP、繰り上がりDP
未知問からこの典型を見つける手掛かり
- 扱う対象
- borrow
- carry
- 整除鎖
- 桁
- 混合基数
- 額面
- 使う手掛かり
- 下位桁から
- 切り上げ
- 切り下げ
- 繰り上がり
- 釣銭
- 保つ不変量
- 整除関係
- 有限carry vector
- 次桁へのcarry
- 端数
- 求めるもの
- 加算制約
- 可解性
- 最小枚数
- 解数
- 適用しない条件
- tight
- 文字列automaton
- 未満フラグ
分類・前提・学習成果
分類と直接の前提
概念上の親: DP状態と遷移
関連する典型
- 上限制約付き桁DP: 上限との接頭辞一致を保つ桁DPと、下位桁から繰り上がりだけを渡す混合基数DPを区別する。
学習成果と学習単位
整除鎖の端数または加算式を下位桁から処理し、切り上げ・切り下げや次桁へのcarryだけを状態にした遷移を設計できる。
繰り上がり・借り・混合基数を状態にするDPで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。