phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

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
というのを更新していく感じで書いていた


しかし、降る場合について、右から登ってくるルートを考慮できておらず、
f:id:phyllo_algo:20171111125323p:plain
のような場合、「地点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]の小さい方。