Overview

This is a dynamic programming (DP) problem where we sequentially compute the “minimum fatigue” to reach each point.
Since you can only move 1 step or 2 steps ahead, the optimal value at each point can be updated using only the optimal values of the two immediately preceding points.

Analysis

First, there are only two ways to reach point \(i\):

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

This structure of “only two transitions” is a classic DP pattern.

DP Definition

Let \(dp[i]\) be “the minimum fatigue to reach point \(i\) from point \(1\)” (using 1-indexed notation for explanation).

Then, the transition to point \(i\) takes the smaller of:

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

Therefore:

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

Why a Naive Approach Fails

If you enumerate all paths using DFS/BFS, the number of paths grows exponentially since there are 2 branches at each step (approximately Fibonacci growth).
For \(N \le 5\times10^5\), this is far too slow.

With DP, we only process each point once, solving the problem in linear time.

Further Memory Optimization

The transition only requires \(dp[i-1]\) and \(dp[i-2]\).
Therefore, instead of maintaining the entire array, just 2 variables (dp0, dp1 in the code) are sufficient.

Algorithm

1. Read the input.
2. Set the base cases:
   • \(dp[1]=0\)
   • \(dp[2]=\max(A_2-A_1, 0)\)
3. For \(i=3\) to \(N\), compute in order:
   • Cost of coming from 1 step before
   • Cost of coming from 2 steps before
   • The minimum of those as the current \(dp[i]\)
4. Proceed while updating the 2 variables.
5. Output the final value (minimum fatigue at point \(N\)).

In the implementation, since we use a 0-indexed array, the loop is for i in range(2, N):, where: - A[i-1] corresponds to 1 step before - A[i-2] corresponds to 2 steps before

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding the input array)

Implementation Notes

• Don’t forget to use max(height difference, 0) (fatigue is 0 when going downhill).

• Handling \(N=2\) separately first makes the code clearer and safer.

• Since values can be large (the cumulative sum can grow large), Python’s integer type handles this without issues.

• Using sys.stdin.readline for fast input is also effective for this problem where \(N\) can be large.

  Source Code

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()

---

This editorial was generated by gpt-5.3-codex.