Overview

This is a problem where you can jump from stone 1 to stone N, moving up to K stones ahead in a single jump, and the goal is to minimize the total sum of values of the stones you pass through.

Analysis

In a naive dynamic programming (DP) approach, for each stone i, we need to find the minimum cost among the up to K previous stones. In this case, computing each state takes O(K), resulting in an overall time complexity of O(NK). Given the constraints where N and K can be up to \(10^6\), this will result in TLE (Time Limit Exceeded).

To address this, we use the sliding window minimum technique. When computing the DP array, by efficiently maintaining the minimum value within the most recent K elements, we can process each step in constant time.

Algorithm

1. Prepare a DP array and initialize with dp[0] = A0
2. Use a deque (double-ended queue) to manage the index with the minimum DP value within the most recent K elements
3. For each stone i (1 ≤ i < N):
   • Remove the front of the deque if it is out of range (less than i-K)
   • Compute dp[i] = dp[front of deque] + A[i]
   • Remove indices from the back of the deque that have DP values greater than or equal to dp[i], then add i
4. The final answer is dp[N-1], the minimum cost

The deque always maintains indices in a “monotonically increasing” order of their DP values. This ensures that the minimum value within the range is always at the front.

Complexity

• Time complexity: \(O(N)\) — Each stone is added to the deque at most once and removed at most once
• Space complexity: \(O(N)\) — The DP array and deque size are proportional to N

Implementation Notes

• The deque stores indices, and actual values are referenced from the DP array

• The out-of-range check is performed with dq[0] < i - k (removing indices less than i-k)

• When managing the deque, “before adding a new value, remove all values greater than it from the back” to maintain monotonicity

• Since the implementation uses 0-indexed arrays, the final answer is dp[n-1]

  Source Code

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    k = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    dp = [0] * n
    dq = deque()
    dq.append(0)
    dp[0] = A[0]
    
    for i in range(1, n):
        while dq and dq[0] < i - k:
            dq.popleft()
            
        dp[i] = dp[dq[0]] + A[i]
        
        while dq and dp[i] <= dp[dq[-1]]:
            dq.pop()
        dq.append(i)
        
    print(dp[n-1])

if __name__ == "__main__":
    main()

---

This editorial was generated by deepseekv3.