时空漫游者的能量跳跃

题意

一条线性路径上有 个能量信标（编号 到 ），每个信标有一个能量值（可正可负）。从信标 出发，可以跳到前方距离 以内的任意信标（即 ）。从信标 出发跳到信标 ，求路径上收集到的最大能量总和。

思路

拿到这题，第一反应是什么？

从起点到终点，每一步最多跳 格，要求路径上经过的信标能量之和最大——这不就是一个经典的 DP 模型吗？

定义 为从信标 出发到达信标 时能收集到的最大能量。转移方程很直接：

$$

也就是说，到达 的最优方案 = 自身的能量 + 前面 个位置中 值最大的那个。

暴力做法每个位置回头扫 个，总复杂度 。能不能更快？

注意到我们每次要的是一个「滑动窗口内的最大值」——窗口大小为 ，窗口随 向右滑动。这正好是单调队列的经典应用场景。

维护一个单调递减的双端队列，队头始终是当前窗口内 值最大的下标。每次：

  1. 弹出队头过期元素（下标 ）
  2. 用队头的 值转移得到
  3. 从队尾弹出所有 值 的元素，再将 入队

这样每个元素最多入队出队各一次，整体 。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int k, n;
    scanf("%d%d", &k, &n);
    vector<long long> e(n);
    for(int i = 0; i < n; i++) scanf("%lld", &e[i]);
    vector<long long> dp(n);
    dp[0] = e[0];
    deque<int> dq;
    dq.push_back(0);
    for(int i = 1; i < n; i++){
        while(!dq.empty() && dq.front() < i - k) dq.pop_front();
        dp[i] = e[i] + dp[dq.front()];
        while(!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back();
        dq.push_back(i);
    }
    printf("%lld\n", dp[n-1]);
    return 0;
}

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine().trim());
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        long[] e = new long[n];
        for (int i = 0; i < n; i++) e[i] = Long.parseLong(st.nextToken());
        long[] dp = new long[n];
        dp[0] = e[0];
        Deque<Integer> dq = new ArrayDeque<>();
        dq.addLast(0);
        for (int i = 1; i < n; i++) {
            while (!dq.isEmpty() && dq.peekFirst() < i - k) dq.pollFirst();
            dp[i] = e[i] + dp[dq.peekFirst()];
            while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) dq.pollLast();
            dq.addLast(i);
        }
        System.out.println(dp[n - 1]);
    }
}

import sys
from collections import deque

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

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const k = parseInt(lines[0]);
    const n = parseInt(lines[1]);
    const e = lines[2].split(' ').map(Number);
    const dp = new Array(n).fill(0);
    dp[0] = e[0];
    const dq = [];
    let head = 0;
    dq.push(0);
    for (let i = 1; i < n; i++) {
        while (head < dq.length && dq[head] < i - k) head++;
        dp[i] = e[i] + dp[dq[head]];
        while (head < dq.length && dp[dq[dq.length - 1]] <= dp[i]) dq.pop();
        dq.push(i);
    }
    console.log(dp[n - 1]);
});

复杂度

  • 时间复杂度：，每个元素入队出队各至多一次。
  • 空间复杂度：，存储 数组和单调队列。