Official
F - Hammer 2 Editorial by physics0523
原点、ゴール、壁、ハンマーの \(4\) つを総称して イベント と呼びます。
経験した(原点やゴールに到着した、壁を壊した、ハンマーを拾った) イベントのうち、最も左のものを \(L\) 、最も右のものを \(R\) と呼ぶことにします。
すると、高橋くんが以下の行動を繰り返すこと以外は考えなくてよいことが分かります。
- \(L\) よりひとつ左のイベントの地点まで移動し、そのイベントを行う。
- \(R\) よりひとつ右のイベントの地点まで移動し、そのイベントを行う。
これをそのまま DP に起こすことを考えます。
\(dp[L][R][\) 現在 \((L,R)\) のどちらの地点にいるか \(]=\{\) ゴールに着くまでの移動距離の最小値 \(\}\) を行えばよいです。
壁を壊す以外のイベントは常に行うことができますが、壁を壊す時だけはそのイベントが実行可能か (その壁に対応するハンマーを持っているか) を調べる必要があります。このことはそう難しくなく、 \(L\) と \(R\) の間に対応するハンマーを拾うイベントがあるかを調べればよいです。
計算量は時間空間ともに \(O(N^2)\) です。
posted:
last update: