题解 | 时空漫游者的能量跳跃

import java.util.*;
import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());
        int[] e = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            e[i] = Integer.parseInt(st.nextToken());
        }
        int[] dp = new int[n];
        dp[0] = e[0];
        Deque<Integer> q = new ArrayDeque<>();
        q.addLast(0);
        for(int i=1;i<n;i++){
            while(!q.isEmpty() && q.peekFirst()<i-k){
                q.pollFirst();
            }
            dp[i]=dp[q.peekFirst()]+e[i];
            while(!q.isEmpty() && dp[q.peekLast()]<dp[i]){
                q.pollLast();
            }
            q.addLast(i);
        }
        
        System.out.println(dp[n-1]);
    }
}