prefix分割DP
列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。
この典型を扱う単元: prefix分割DP
検索別名: prefix分割DP、最後のブロックを固定
未知問からこの典型を見つける手掛かり
- 扱う対象
- prefix
- 切れ目
- 連続ブロック
- 使う手掛かり
- 分割を数える
- 到着順にまとめる
- 最後の区間を固定
- 保つ不変量
- 処理済みprefix
- 最後の切れ目の一意性
- 求めるもの
- 分割の最適値
- 分割数
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: DP状態と遷移
関連する典型
学習成果と学習単位
列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
prefix分割DPで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC285 E「Work or Rest」 公式問題主題: prefix分割DP / 主タグ
- ABC288 F「Integer Division」 公式問題主題: prefix分割DP / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC228 H「Histogram」 公式問題主題: Convex Hull Trick・直線包絡 / 補助タグ
- ABC230 F「Predilection」 公式問題主題: prefix分割DP / 主タグ
- ABC234 G「Divide a Sequence」 公式問題主題: 支配関係から不要な候補を単調stack・queueで削る / 補助タグ
- ABC262 Ex「Max Limited Sequence」 公式問題主題: prefix分割DP / 主タグ
- ABC285 E「Work or Rest」 公式問題主題: prefix分割DP / 主タグ
- ABC288 F「Integer Division」 公式問題主題: prefix分割DP / 主タグ
- ABC305 Ex「Shojin」 公式問題主題: Lagrangian relaxation・Aliens trick / 補助タグ
技能・出典
主題: Lagrangian relaxation・Aliens trick
主タグ: Lagrangian relaxation・Aliens trick / 補助タグ: prefix分割DP、貪欲法と交換論
- ABC374 F「Shipping」 公式問題主題: prefix分割DP / 主タグ
- ABC466 E「Range Flip」 公式問題主題: prefix分割DP / 主タグ