概要

各地点までの「最小疲労」を順に求める動的計画法（DP）の問題です。
1歩先・2歩先にしか進めないので、各地点の最適値は直前2地点の最適値だけで更新できます。

考察

まず、地点 \(i\) に到達する方法は次の2通りしかありません。

• 地点 \(i-1\) から 1 歩で来る
• 地点 \(i-2\) から 2 歩で来る

この「遷移が2通りだけ」という構造はDPの典型です。

DPの定義

\(dp[i]\) を「地点 \(1\) から地点 \(i\) まで到達する最小疲労」とします（説明上は1-indexed）。

すると、地点 \(i\) への遷移は

• \(dp[i-1] + \max(A_i - A_{i-1}, 0)\)
• \(dp[i-2] + \max(A_i - A_{i-2}, 0)\)

の小さい方です。よって

[ dp[i] = \min\left( dp[i-1] + \max(Ai - A{i-1}, 0), dp[i-2] + \max(Ai - A{i-2}, 0) \right) ]

なぜ素朴解法はだめか

全経路をDFS/BFSで列挙すると、分岐が毎回2通りあるため経路数は指数的に増えます（ほぼフィボナッチ増加）。
\(N \le 5\times10^5\) では到底間に合いません。

DPなら各地点を1回ずつ処理するだけで済み、線形時間で解けます。

さらにメモリ最適化できる

遷移に必要なのは \(dp[i-1]\) と \(dp[i-2]\) のみです。
したがって配列全体を持たず、2変数（コード中の dp0, dp1）で十分です。

アルゴリズム

1. 入力を読む。
2. 基本ケースを設定する。
   • \(dp[1]=0\)
   • \(dp[2]=\max(A_2-A_1, 0)\)
3. \(i=3\) から \(N\) まで順に、次を計算：
   • 1歩前から来るコスト
   • 2歩前から来るコスト
   • その最小値を現在の \(dp[i]\)
4. 2変数を更新しながら進める。
5. 最後の値（地点 \(N\) の最小疲労）を出力。

実装では0-index配列なので、ループは for i in range(2, N): となり、 - A[i-1] が1歩前 - A[i-2] が2歩前
に対応しています。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力配列を除く）

実装のポイント

• max(高さ差, 0) を忘れず使う（下りは疲労0）。

• N=2 は先に処理すると分かりやすく安全。

• 値が大きいので（最大で累積が大きくなる可能性あり）Pythonの整数型で問題なし。
  

• sys.stdin.readline を使って高速入力にしている点も、\(N\) が大きい本問では有効です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    A = list(map(int, input().split()))

    INF = 10**30
    dp0 = 0      # dp[i-2]
    dp1 = max(A[1] - A[0], 0)  # dp[i-1] for i=2 (1-indexed)

    if N == 2:
        print(dp1)
        return

    for i in range(2, N):
        cost1 = dp1 + max(A[i] - A[i - 1], 0)
        cost2 = dp0 + max(A[i] - A[i - 2], 0)
        cur = cost1 if cost1 < cost2 else cost2
        dp0, dp1 = dp1, cur

    print(dp1)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。