Overview

This is a dynamic programming (DP) problem where we sequentially compute the “minimum fatigue” to reach each point. Since point \(i\) can only be reached from point \(i-1\) or point \(i-2\), we can solve it by updating the minimum value from previous states.

Analysis

In this problem, we want to minimize the total fatigue when traveling from point \(1\) to point \(N\).

The possible moves are:

• Move to the point 1 step ahead
• Move to the point 2 steps ahead

So there are at most 2 ways to reach each point. This pattern where “the optimal solution at a certain point is determined from the optimal solutions at slightly earlier points” is a classic scenario for dynamic programming.

Key Observation

The fatigue when moving from point \(i\) to point \(j\) is:

• If \(A_j > A_i\), then \(A_j - A_i\)
• If \(A_j \leq A_i\), then \(0\)

In other words, expressed as a formula: \( \max(A_j - A_i, 0) \).

For example, if the elevations are:

• \(10 \to 15\), the fatigue is \(5\)
• \(15 \to 10\), the fatigue is \(0\)

The key point is that fatigue does not increase when going downhill.

Why a Naive Approach Doesn’t Work

If we exhaustively search “whether to take 1 step or 2 steps” at each point, the number of paths grows exponentially. Since \(N\) can be as large as \(5 \times 10^5\), trying all paths is far too slow.

How to Solve It

We use DP to record the minimum fatigue to reach each point.

Define \(dp[i]\) as: “The minimum fatigue to reach point \(i+1\) from point \(1\)” (managed as 0-indexed to match the code).

Then, point \(i\) can be reached in the following 2 ways:

• Coming from point \(i-1\) in 1 step
• Coming from point \(i-2\) in 2 steps

Therefore, the transition is:

$

dp[i]

\min\Bigl( dp[i-1] + \max(Ai - A{i-1}, 0), \; dp[i-2] + \max(Ai - A{i-2}, 0) \Bigr) $

(for \(i \geq 2\)).

The initial value is \(0\) fatigue at the starting point (point \(1\)):

\( dp[0] = 0 \)

Concrete Example

Consider \(A = [10, 30, 20, 40]\).

• \(dp[0] = 0\)
• \(dp[1] = dp[0] + \max(30 - 10, 0) = 20\)
• \(dp[2]\)
  • \(1 \to 2 \to 3\): \(20 + \max(20 - 30, 0) = 20\)
  • \(1 \to 3\): \(0 + \max(20 - 10, 0) = 10\)
  • Thus \(dp[2] = 10\)
• \(dp[3]\)
  • \(2 \to 4\): \(20 + \max(40 - 30, 0) = 30\)
  • \(3 \to 4\): \(10 + \max(40 - 20, 0) = 30\)
  • Thus \(dp[3] = 30\)

The answer is \(30\).

Algorithm

1. Prepare an array \(dp\) and initialize all values to a sufficiently large number.
2. Set \(dp[0] = 0\).
3. For \(i = 1\) to \(N-1\), do the following:
   • Coming from point \(i-1\): \( dp[i] = \min(dp[i],\ dp[i-1] + \max(A_i - A_{i-1}, 0)) \)
   • If \(i \geq 2\), coming from point \(i-2\): \( dp[i] = \min(dp[i],\ dp[i-2] + \max(A_i - A_{i-2}, 0)) \)
4. Output \(dp[N-1]\).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• The fatigue increase must always be calculated as \( \max(A_j - A_i, 0) \).

• Arrays in Python are 0-indexed, so “point \(1\)” in the problem statement corresponds to A[0] in the code.

• The INF used for initialization can be any sufficiently large value. The code uses 10**30.

• Since this problem only uses the previous 2 states, the space can theoretically be reduced to \(O(1)\), but \(O(N)\) is more than sufficient within the constraints.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    
    INF = 10**30
    dp = [INF] * N
    dp[0] = 0
    
    for i in range(1, N):
        dp[i] = min(dp[i], dp[i - 1] + max(A[i] - A[i - 1], 0))
        if i >= 2:
            dp[i] = min(dp[i], dp[i - 2] + max(A[i] - A[i - 2], 0))
    
    print(dp[-1])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.