yukicoder No.595 登山
問題
N個の地点が1~Nまで順番に直線上に並んでおり、地点iの標高がH_iで与えられる。
地点1からスタートし、すべての地点に1回以上訪れたい。終了地点はどこでもよい。
移動は2種類あり、「隣接地点に移動する場合、登る方向に移動する場合のみ標高の差」か「ワープによる任意地点への移動にはP」のエネルギーがかかる。
最小エネルギーを求めよ。
制約
2 <= N <= 2*10^5
0 <= P <= 10^9
0 <= H_i <= 10^9
解法
コンテスト時間中は、左から順に、隣が登る場合はワープして降ってくるor登るか、隣が降る場合は隣に降るかその地点にワープする感じで、
dp[i][x] := i地点までの最小エネルギーで、i地点にいる場合x=0、いない場合x=1
というのを更新していく感じで書いていた
しかし、降る場合について、右から登ってくるルートを考慮できておらず、
のような場合、「地点1→地点3→地点2→地点1→地点4→地点5→地点7→地点6→地点5」というルートを考えてしまっていた。
(この場合の最小ルートは「地点1→地点3→地点2→(地点1)→地点7→地点6→地点5→地点4」というルート)
左からも右からも降るか登るかすべてを考える必要がある。左右どちらからくるかを区別すると、
dp[i][x] := i地点に左から訪れている場合x=0、右から訪れている場合x=1の場合の、1~i地点までの最小エネルギー
とすれば、i-1とiの地点でのdpの値を考えて、
dp[0][0] = 0; REP(i,1,N){ // i-1 i // -> & -> dp[i][0] = min(dp[i][0], dp[i-1][0] + max(0LL,H[i]-H[i-1])); dp[i][0] = min(dp[i][0], dp[i-1][0] + P); // -> & <- dp[i][1] = min(dp[i][1], dp[i-1][0] + P); // <- & -> dp[i][0] = min(dp[i][0], dp[i-1][1] + P); // <- & <- dp[i][1] = min(dp[i][1], dp[i-1][1] + max(0LL,H[i-1]-H[i])); dp[i][1] = min(dp[i][1], dp[i-1][1] + P); }
のような遷移を考えられる。
答えはdp[N-1][0]かdp[N-1][1]の小さい方。