Overview

This problem asks us to minimize the total cost of stones landed on when moving from stone \(1\) to stone \(N\), jumping to at most \(K\) stones ahead at each step. We solve it efficiently by combining dynamic programming (DP) with a sliding window minimum (monotone deque).

Analysis

DP Formulation

Let \(dp[i]\) be the minimum cumulative cost to reach stone \(i\). Since stone \(i\) can be reached by jumping from any stone between \(\max(1, i-K)\) and \(i-1\), the following recurrence holds:

\[dp[i] = A_i + \min_{j \in [\max(0,\, i-K),\, i-1]} dp[j]\]

The initial value is \(dp[0] = A_1\) (corresponding to stone \(1\) in 0-indexed notation).

Problem with the Naive Approach

If we naively compute the minimum of \(dp[j]\) (over up to \(K\) values of \(j\)) for each \(dp[i]\), the overall time complexity becomes \(O(NK)\). Since \(N\) can be up to \(10^6\) and \(K\) can be up to \(N-1\), the worst case is \(O(N^2)\), which will result in TLE.

Solution: Sliding Window Minimum

The operation “efficiently retrieve the minimum \(dp\) value among the previous up to \(K\) elements” can be processed in \(O(1)\) amortized time per element using a Monotone Deque.

Algorithm

A monotone deque is a data structure maintained so that the front of the deque always holds the index of the minimum value within the window.

Specific procedure:

1. Set \(dp[0] = A_0\) and push index \(0\) into the deque.
2. For \(i = 1, 2, \ldots, N-1\), repeat the following:
   • Remove elements outside the window: If the front of the deque is less than \(i - K\) (i.e., outside the jump range), remove it from the front.
   • Update DP: Let \(f\) be the index at the front of the deque, then \(dp[i] = A_i + dp[f]\).
   • Maintain monotonicity: Remove indices from the back of the deque while their \(dp\) values are greater than or equal to \(dp[i]\), then append \(i\) to the back.
3. \(dp[N-1]\) is the answer.

Concrete Example

For \(N = 5,\, K = 2,\, A = [3, 1, 5, 2, 4]\):

\(i\)	Transition source range	\(dp\) at deque front	\(dp[i]\)
0	—	—	\(3\)
1	\(\{0\}\)	\(dp[0]=3\)	\(1+3=4\)
2	\(\{0,1\}\)	\(dp[0]=3\)	\(5+3=8\)
3	\(\{1,2\}\)	\(dp[1]=4\)	\(2+4=6\)
4	\(\{2,3\}\)	\(dp[3]=6\)	\(4+6=10\)

The answer is \(dp[4] = 10\).

Complexity

• Time complexity: \(O(N)\) — Each index is added to and removed from the deque at most once, so the total is \(O(N)\).
• Space complexity: \(O(N)\) — The \(dp\) array and the deque each use at most \(O(N)\) space.

Implementation Notes

• Store indices in the deque, and compare \(dp\) values using those indices. This allows us to handle both the window boundary check and the DP value comparison.

• The condition for removing from the back of the deque is dp[dq[-1]] >= dp[i] (including equality). By including equality, when there are multiple elements with the same value, only the newer one is kept, making it less likely to be removed from the window prematurely.

• In Python, collections.deque’s popleft() / pop() / append() are all \(O(1)\), enabling efficient implementation.

• Since \(N\) can be as large as \(10^6\), we use sys.stdin.read() to read all input at once, speeding up I/O.

  Source Code

import sys
from collections import deque

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    A = list(map(int, input_data[2:2+N]))
    
    # dp[i] = minimum cost to reach stone i
    # dp[i] = A[i] + min(dp[j] for j in range(max(0, i-K), i))
    # Use a sliding window minimum with a deque
    
    dp = [0] * N
    dp[0] = A[0]
    
    dq = deque()  # stores indices, dp values in increasing order
    dq.append(0)
    
    for i in range(1, N):
        # Remove elements out of window
        while dq and dq[0] < i - K:
            dq.popleft()
        
        dp[i] = A[i] + dp[dq[0]]
        
        # Maintain monotonic deque
        while dq and dp[dq[-1]] >= dp[i]:
            dq.pop()
        dq.append(i)
    
    print(dp[N-1])

main()

---

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