DP状態空間を絞る
状態空間を上手に削減する系の問題 問題へのリンク editorial 問題概要 種類の長方形形状 () をしたスタンプがある (それぞれ「赤」「緑」「青」の 3 種類がある)。 これらを使って 4 × 4 のグリッド上に所望の模様を作りたい。グリッドからはみ出して押して…
AOJ
HUPC
数え上げ問題
操作によって作れるものの集合を考える(判定関数を考える)
操作
操作後の結果の数え上げ
区間
区間ソート
Greedy
DP
移動可能区間を遷移していく
ナップサックDP
座標圧縮
探索候補を絞る
端点のみを考える
DP状態空間を絞る
比較的素直な考察で解ける問題 問題へのリンク 問題概要 umgくんは 1 次元上の座標 0 にいます。今は時刻 0 です。時刻が 1 進むごとに、今いる座標より 1 大きい座標に移動するか、 1 小さい座標に移動するか、その座標にとどまるかという行動ができます。 …