Overview

This problem asks us to move from point \(1\) to point \(N\) among \(N\) points on a mountain trail, where at each step we can advance to the next point or skip one point ahead, and we want to minimize the total fatigue incurred from uphill segments. This can be solved using dynamic programming (DP).

Analysis

Problem Setup

• From point \(i\), we can advance to point \(i+1\) or point \(i+2\)
• Fatigue \(A_j - A_i\) is added only when going uphill (\(A_j > A_i\))
• No fatigue is incurred for downhill or flat movements (fatigue is \(0\))

Key Insight

If we know the minimum fatigue upon reaching each point, we can compute the transitions from that point onward. This is a classic DP (dynamic programming) pattern.

There are at most two ways to reach point \(i\): coming from point \(i-1\) or coming from point \(i-2\). Therefore, the minimum fatigue at each point can be computed with a constant number of operations.

Concrete Example

For example, if \(A = [10, 30, 15, 40]\) (\(N = 4\)):

• Point 1: Fatigue \(0\) (starting point)
• Point 2: From point 1 → \(\max(30-10, 0) = 20\)
• Point 3: From point 1 → \(\max(15-10, 0) = 5\); from point 2 → \(20 + \max(15-30, 0) = 20\). Minimum is \(5\)
• Point 4: From point 2 → \(20 + \max(40-30, 0) = 30\); from point 3 → \(5 + \max(40-15, 0) = 30\). Minimum is \(30\)

The key point is that by skipping a point, we can sometimes avoid deep valleys and reduce total fatigue.

Algorithm

We use dynamic programming.

1. Define \(dp[i]\) as “the minimum fatigue when traveling from point \(1\) to point \(i+1\)” (0-indexed)
2. Initial value: \(dp[0] = 0\) (fatigue is \(0\) at the starting point)
3. Transition: For each point \(i\), consider moving to point \(i+1\) and point \(i+2\) $\(dp[j] = \min(dp[j],\; dp[i] + \max(A_j - A_i,\; 0))\)\( where \)j \in {i+1, i+2}\( and \)j < N$
4. The answer is \(dp[N-1]\)

Complexity

• Time complexity: \(O(N)\) — We examine at most 2 transition destinations per point
• Space complexity: \(O(N)\) — Size of the DP array

Implementation Notes

• The standard approach is to initialize the DP array with a sufficiently large value (\(\infty\)) and set \(dp[0] = 0\).

• Don’t forget the bounds check (if j < N) to ensure the transition destination index does not exceed \(N\).

• By using sys.stdin.buffer.read() to read all input at once, even inputs of size \(N = 5 \times 10^5\) can be processed efficiently in Python.

• The cost computation max(A[j] - A[i], 0) concisely expresses the problem’s condition: add the elevation difference only when going uphill, and use \(0\) when going downhill.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    A = [int(input_data[i + 1]) for i in range(N)]
    
    INF = float('inf')
    dp = [INF] * N
    dp[0] = 0
    
    for i in range(N):
        if dp[i] == INF:
            continue
        for j in (i + 1, i + 2):
            if j < N:
                cost = max(A[j] - A[i], 0)
                if dp[j] > dp[i] + cost:
                    dp[j] = dp[i] + cost
    
    print(dp[N - 1])

main()

---

This editorial was generated by claude4.6opus-thinking.