典型タグ

frontier/profile DP・境界状態圧縮

走査済み領域と未走査領域の境界だけに未来へ影響する色・値の使用済みフラグ・接続partitionを保持し、必要なら同値な接続ラベルを正規化して幅指数で遷移する。

この典型を扱う単元: frontier/profile DP・境界状態圧縮

検索別名: frontier DP、plug DP、profile DP

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

扱う対象
  • connectivity partition
  • grid sweep frontier
  • profile mask
  • 帯状matchingの使用済み値
使う手掛かり
  • 一辺だけ小さい盤面
  • 対角近傍に限られる許可辺
  • 局所制約と全体連結性
保つ不変量
  • closed component condition
  • future interface only
  • 窓外の使用済み値を忘れる
求めるもの
  • 帯状部分matchingの計数
  • 幅指数DP
  • 盤面数え上げ
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

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

関連する典型

  • 部分集合・bitmask状態DP: 集合の使用済みフラグを状態にする点は共通する。境界DPでは未来へ影響しない要素を忘れ、指数部分を全要素数ではなく境界幅に限定できることをさらに証明する。

学習成果と学習単位

  • 未処理領域へ影響する境界上の色・使用済みフラグ・接続partitionだけを残し、窓外の情報を忘れられることを証明して幅指数のprofile DPを設計できる。

    frontier/profile DP・境界状態圧縮で学ぶ

代表問題

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

関連問題

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