DPの最小十分状態
将来の選択肢と答えが同じprefixを同一状態に縮約する。
この典型を扱う単元: 最小十分状態からDPを設計する
検索別名: minimal sufficient state、state-compressed DP、状態圧縮DP、同値性によるDP状態圧縮
未知問からこの典型を見つける手掛かり
- 扱う対象
- prefix
- 未来
- 状態
- 過去
- 使う手掛かり
- \bdp\b
- 動的計画
- 遷移
- 保つ不変量
- 十分
- 同一視
- 圧縮
- 最後
- 求めるもの
- 可否
- 場合の数
- 最適
- 状態数
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC375 E「3 Team Division」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC232 E「Rook Path」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC296 Ex「Unite」 公式問題主題: frontier/profile DP・境界状態圧縮 / 補助タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC215 E「Chain Contestant」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC217 G「Groups」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC227 E「Swap」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC229 F「Make Bipartite」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC232 E「Rook Path」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC236 E「Average and Median」 公式問題主題: fractional programming・比率parametric search / 補助タグ
- ABC237 F「|LIS| = 3」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC244 E「King Bombee」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC247 F「Cards」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC251 E「Takahashi and Animals」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC264 F「Monochromatic Path」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC265 E「Warp」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC273 G「Row Column Sums 2」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC279 G「At Most 2 Colors」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC281 G「Farthest City」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC282 G「Similar Permutation」 公式問題主題: DP遷移を因数分解・集約して加速する / 補助タグ
- ABC283 E「Don't Isolate Elements」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC296 Ex「Unite」 公式問題主題: frontier/profile DP・境界状態圧縮 / 補助タグ
- ABC307 E「Distinct Adjacent」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC309 E「Family and Insurance」 公式問題主題: 根付き木DP・部分木集約 / 補助タグ
- ABC310 E「NAND repeatedly」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC311 E「Defect-free Squares」 公式問題主題: グリッド・多次元表の局所DPを設計する / 主タグ
- ABC311 F「Yet Another Grid Task」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC313 Ex「Group Photo」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC322 E「Product Development」 公式問題主題: 資源・容量DP / 補助タグ
- ABC344 F「Earn to Advance」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC345 E「Colorful Subsequence」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC350 E「Toward 0」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC374 F「Shipping」 公式問題主題: prefix分割DP / 補助タグ
- ABC375 E「3 Team Division」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC376 F「Hands on Ring (Hard)」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC378 G「Everlasting LIDS」 公式問題主題: Robinson–Schensted対応・Young tableau / 補助タグ
技能・出典
主題: Robinson–Schensted対応・Young tableau
主タグ: Robinson–Schensted対応・Young tableau / 補助タグ: DPの最小十分状態
- ABC379 G「Count Grid 3-coloring」 公式問題主題: frontier/profile DP・境界状態圧縮 / 補助タグ
- ABC381 F「1122 Subsequence」 公式問題主題: 部分集合・bitmask状態DP / 補助タグ
- ABC386 F「Operate K」 公式問題主題: 列・subsequence DP / 補助タグ
- ABC388 F「Dangerous Sugoroku」 公式問題主題: 数値半群のconductor以後を一括到達とみなす / 補助タグ
- ABC389 G「Odd Even Graph」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC391 G「Many LCS」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC403 F「Shortest One Formula」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC416 G「Concat (1st)」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC418 G「Binary Operation」 公式問題主題: 有限状態automatonの構成 / 補助タグ
- ABC422 F「Eat and Ride」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC427 E「Wind Cleaning」 公式問題主題: 状態グラフのモデリングと探索 / 補助タグ
- ABC435 F「Cat exercise」 公式問題主題: 大小関係をCartesian treeへ変換する / 補助タグ
技能・出典
主タグ: Cartesian treeによる区間極値分解 / 補助タグ: DPの最小十分状態、単調stack・queueによる支配候補の削除、根付き木DP・部分木集約
- ABC440 G「Haunted House」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC450 F「Strongly Connected 2」 公式問題主題: 最小十分状態からDPを設計する / 主タグ
- ABC457 F「Second Gap」 公式問題主題: DP遷移を因数分解・集約して加速する / 補助タグ
- ABC462 F「More ABC」 公式問題主題: 最小十分状態からDPを設計する / 主タグ