資源軸knapsack DP
容量・時間・個数などの有界資源を軸に選択の価値を更新する。
この典型を扱う単元: 資源・容量DP
検索別名: knapsack DP、ナップサックDP、部分和DP
未知問からこの典型を見つける手掛かり
- 扱う対象
- 上限
- 価値
- 容量
- 資源
- 重さ
- 使う手掛かり
- 使う
- 選ぶ
- 選択
- 配る
- 保つ不変量
- 以下
- 使用済み
- 合計
- 求めるもの
- 可否
- 最大価値
- 最小コスト
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC321 F「#(subset sum = K) with Add and Erase」 公式問題主題: 資源・容量DP / 主タグ
- ABC322 E「Product Development」 公式問題主題: 資源・容量DP / 主タグ
- ABC383 F「Diversity」 公式問題主題: 資源・容量DP / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC216 F「Max Sum Counting」 公式問題主題: 資源・容量DP / 主タグ
- ABC222 E「Red and Blue Tree」 公式問題主題: 資源・容量DP / 主タグ
- ABC269 G「Reversible Cards 2」 公式問題主題: 資源・容量DP / 主タグ
- ABC275 F「Erase Subarrays」 公式問題主題: 資源・容量DP / 主タグ
- ABC287 F「Components」 公式問題主題: 根付き木DP・部分木集約 / 補助タグ
- ABC288 E「Wish List」 公式問題主題: 資源・容量DP / 主タグ
- ABC290 Ex「Bow Meow Optimization」 公式問題主題: 交換論から選択順を導く / 補助タグ
- ABC307 G「Approximate Equalization」 公式問題主題: 資源・容量DP / 主タグ
- ABC310 Ex「Negative Cost」 公式問題主題: 大容量unbounded knapsackのeventual linearity / 補助タグ
- ABC311 Ex「Many Illumination Plans」 公式問題主題: 資源DPを引数で渡すHLRecDP / 補助タグ
- ABC320 F「Fuel Round Trip」 公式問題主題: 資源・容量DP / 主タグ
- ABC321 F「#(subset sum = K) with Add and Erase」 公式問題主題: 資源・容量DP / 主タグ
- ABC322 E「Product Development」 公式問題主題: 資源・容量DP / 主タグ
- ABC325 F「Sensor Optimization Dilemma」 公式問題主題: 資源・容量DP / 主タグ
- ABC332 G「Not Too Many Balls」 公式問題主題: 最大流・最小カット / 補助タグ
- ABC341 F「Breakdown」 公式問題主題: 資源・容量DP / 主タグ
- ABC364 E「Maximum Glutton」 公式問題主題: 資源・容量DP / 主タグ
- ABC366 F「Maximum Composition」 公式問題主題: 交換論から選択順を導く / 補助タグ
- ABC373 F「Knapsack with Diminishing Values」 公式問題主題: 分離凸・凹の単調限界値選択 / 補助タグ
- ABC375 E「3 Team Division」 公式問題主題: 最小十分状態からDPを設計する / 補助タグ
- ABC382 E「Expansion Packs」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC383 F「Diversity」 公式問題主題: 資源・容量DP / 主タグ
- ABC390 E「Vitamin Balance」 公式問題主題: 資源・容量DP / 主タグ
- ABC410 E「Battles in a Row」 公式問題主題: 資源・容量DP / 主タグ
- ABC416 F「Paint Tree 2」 公式問題主題: 根付き木DP・部分木集約 / 補助タグ
- ABC419 E「Subarray Sum Divisibility」 公式問題主題: 資源・容量DP / 主タグ
- ABC424 G「Set list」 公式問題主題: 資源・容量DP / 主タグ
- ABC426 G「Range Knapsack Query」 公式問題主題: 再帰分割・分割統治 / 補助タグ
- ABC428 G「Necklace」 公式問題主題: 群作用・軌道数え上げ / 補助タグ
- ABC441 F「Must Buy」 公式問題主題: 資源・容量DP / 主タグ
- ABC461 F「Total Product is N」 公式問題主題: 資源・容量DP / 主タグ