Overview

Given \(N\) points arranged in a line, you repeatedly move to either the next point or the point two ahead. The goal is to minimize the total “elevation difference (uphill only)” incurred during movement.

Analysis

The key insight of this problem is that “the minimum fatigue to reach a given point is determined by the state immediately before it.”

There are only two ways to reach point \(i\): 1. Move 1 step from point \(i-1\) 2. Move 2 steps from point \(i-2\)

To minimize the total fatigue upon reaching point \(i\), we simply choose whichever of these two routes yields a smaller sum of accumulated fatigue plus the fatigue added by the current move.

In this way, breaking a large problem into smaller subproblems (minimum fatigue to each point) and solving them sequentially is a situation where dynamic programming (DP) is extremely effective.

Algorithm

We solve this using dynamic programming.

1. DP Table Definition: Define \(dp[i]\) as “the minimum total fatigue required to reach point \(i\).”
2. Initial Conditions:
   • Point 1: This is the starting point, so \(dp[1] = 0\).
   • Point 2: The only option is to come from point 1, so \(dp[2] = \max(A_2 - A_1, 0)\).
3. Transition Formula: For point \(i\) (\(3 \leq i \leq N\)), set \(dp[i]\) to the smaller of the following two values:
   • Moving from point \(i-1\): \(dp[i-1] + \max(A_i - A_{i-1}, 0)\)
   • Moving from point \(i-2\): \(dp[i-2] + \max(A_i - A_{i-2}, 0)\)

By computing this sequentially from \(i=3\) to \(N\), we can obtain the final answer \(dp[N]\).

Complexity

• Time Complexity: \(O(N)\) Since we compute from point 3 to \(N\) in a single loop, the computation finishes in time proportional to the number of points \(N\). This is sufficiently fast even under the constraint \(N = 5 \times 10^5\).
• Space Complexity: \(O(N)\) The array (DP table) that records the minimum fatigue for each point has size \(N\).

Implementation Notes

• Elevation Difference Calculation: max(A_j - A_i, 0) can be computed using an if statement in Python, or equivalently written as max(0, diff).

• Handling Large Input: Since \(N\) can be large, reading all input at once with sys.stdin.read().split() is faster than repeatedly calling input().

• Index Correspondence: The problem uses points starting from 1, but lists in the program start from index 0. Be careful to implement so that dp[i] corresponds to point i+1.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする
    # sys.stdin.read().split() は大量の数値を読み込む際に効率的です
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 地点の数 N と、各地点の標高 A を取得
    N = int(input_data[0])
    A = list(map(int, input_data[1:]))
    
    # 地点が1つの場合は移動の必要がないため疲労は0（制約上 N >= 2 ですが、念のため）
    if N == 1:
        print(0)
        return
    
    # dp[i] は地点 i+1 に到達するために必要な最小の疲労合計を格納する
    # 0-indexed で管理するため、地点 1 は dp[0], 地点 N は dp[N-1] に対応
    dp = [0] * N
    
    # 初期条件
    # 地点 1 (dp[0]) の疲労は 0
    dp[0] = 0
    
    # 地点 2 (dp[1]) へは地点 1 からのみ到達可能
    diff_0_1 = A[1] - A[0]
    dp[1] = diff_0_1 if diff_0_1 > 0 else 0
    
    # 地点 3 以降の最小疲労を動的計画法で求める
    for i in range(2, N):
        # 地点 i-1 から移動する場合の疲労
        # 移動先 A[i] が現在地 A[i-1] より高い場合のみその差が加算される
        diff1 = A[i] - A[i-1]
        cost1 = dp[i-1] + (diff1 if diff1 > 0 else 0)
        
        # 地点 i-2 から移動する場合の疲労
        # 移動先 A[i] が現在地 A[i-2] より高い場合のみその差が加算される
        diff2 = A[i] - A[i-2]
        cost2 = dp[i-2] + (diff2 if diff2 > 0 else 0)
        
        # 2つの移動経路のうち、疲労が小さくなる方を選択
        if cost1 < cost2:
            dp[i] = cost1
        else:
            dp[i] = cost2
            
    # 地点 N (dp[N-1]) に到達したときの最小疲労を出力
    print(dp[N-1])

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.