登山 [yukicoder No.595] - はまやんはまやんはまやん

解法

公式解説がとても詳しい。
以下、それと同じことを違う言葉で説明する。
　
dpをする。
dp[i][dir] := i番目(0-indexed)の頂点にいてdir向き(=0:→, =1:←)の区間にいる途中の最小コスト
初期化はdp[0][0]=0, dp[other]=INFとする。

dp[i][0],dp[i][1]からの遷移は4種類考えられるので、それをやる。

->を伸ばす遷移
- これは横に伸ばすだけなので、普通にコストを足す
- しかし、コストよりもワープコストの方が小さいなら、ワープで移動する
- dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + min(P, max(H[i + 1] - H[i], 0LL)));
今まで->だったのを<-とする遷移
- ワープしないと移動できないので、ワープコストだけかかる
- dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + P);
<-を伸ばす遷移
- 「->を伸ばす遷移」と同様
- dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + min(P, max(H[i] - H[i + 1], 0LL)));
今まで<-だったのを->とする遷移
- これも「今まで->だったのを<-とする遷移」と同様
- dp[i + 1][0] = min(dp[i + 1][0], dp[i][1] + P);

　
あとは、dp[N-1][0]とdp[N-1][1]の小さいほうが答え。
これは最終的な終了地点はどこでもいいからである。

typedef long long ll;
#define INF 1LL<<60
int N; ll P, H[201010];
ll dp[201010][2];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> P;
    rep(i, 0, N) cin >> H[i];

    rep(i, 0, 201010) rep(dir, 0, 2) dp[i][dir] = INF;
    dp[0][0] = 0;

    rep(i, 0, N - 1) {
        // ->を伸ばす遷移
        dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + min(P, max(H[i + 1] - H[i], 0LL)));
        
        // 今まで->だったのを<-とする遷移
        dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + P);

        // <-を伸ばす遷移
        dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + min(P, max(H[i] - H[i + 1], 0LL)));

        // 今まで<-だったのを->とする遷移
        dp[i + 1][0] = min(dp[i + 1][0], dp[i][1] + P);
    }

    ll ans = min(dp[N - 1][0], dp[N - 1][1]);
    cout << ans << endl;
}