思路:单调队列优化的动态规划

根据题目意思，我们可以想到一种很简单的动态规划方法：从左到右dp，对于每一个i , 去看$[i-k,i-1]$ 这个下标范围内的最大可能的$dp$值，假设是$x$ , 那么就是$dp[i] = x + a[i]$

这样复杂度是$O(nk)$的不能拿满分，所以先学习一下下面两个算法:

先学习一下单调队列

在学习下单调队列优化动态规划

我们可以使用单调队列来维护$[i-k,i-1]$ 内的dp最大值。 复杂度为$O(n)$

C++

#include <iostream>
#include <deque>
using namespace std;

int getAns(int arr[], int n, int k) {
    deque<pair<int, int>> q;
    int dp[n];
    dp[0] = arr[0];
    q.push_back(make_pair(0, dp[0]));

    for (int i = 1; i < n; i++) {
        // 移除窗口范围之外的元素
        while (!q.empty() && q.front().first < i - k) {
            q.pop_front();
        }
        
        // 计算dp[i]，取队列中的最大值加上当前元素的值
        dp[i] = arr[i] + q.front().second;

        // 移除队列中小于等于dp[i]的元素
        while (!q.empty() && q.back().second <= dp[i]) {
            q.pop_back();
        }

        // 将当前dp[i]加入队列中
        q.push_back(make_pair(i, dp[i]));
    }

    return dp[n - 1];
}

int main() {
    int n;
    cin >> n;

    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int k;
    cin >> k;

    cout << getAns(arr, n, k) << endl;
    return 0;
}

Java

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];

        // 读取输入数组
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int k = sc.nextInt();
        System.out.println(getAns(arr, n, k));
        return;
    }
    // 获取最终结果
    public static int getAns(int[] arr, int n, int k) {
        Queue<Integer[]> q = new LinkedList<>();
        int[] dp = new int[n];
        dp[0] = arr[0];
        q.add(new Integer[]{0, dp[0]});

        for (int i = 1; i < n; i++) {
            // 移除超出窗口范围的元素
	        while (!q.isEmpty() && q.peek()[0] < i - k) {
	            q.poll();
	        }
            // 计算dp[i]，取队列中的最大值+当前元素的值
            dp[i] = arr[i] + q.peek()[1];

            // 移除队列中小于等于dp[i]的元素
        while (!q.isEmpty() && q.peek()[1] <= dp[i]) {
            q.poll();
        }

            // 将当前dp[i]加入队列中
            q.add(new Integer[]{i, dp[i]});
        }

        return dp[n - 1];
    }
}

Python

from collections import deque

def get_ans(arr, n, k):
    q = deque()
    dp = [0] * n
    dp[0] = arr[0]
    q.append((0, dp[0]))

    for i in range(1, n):
        # 移除窗口范围之外的元素
        while q and q[0][0] < i - k:
            q.popleft()

        # 计算dp[i]，取队列中的最大值加上当前元素的值
        dp[i] = arr[i] + q[0][1]

        # 移除队列中小于等于dp[i]的元素
        while q and q[-1][1] <= dp[i]:
            q.pop()

        # 将当前dp[i]加入队列中
        q.append((i, dp[i]))

    return dp[-1]

n = int(input())
arr = list(map(int, input().split()))
k = int(input())

print(get_ans(arr, n, k))

JavaScript

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');
    const n = parseInt(lines[0]);
    const arr = lines[1].split(' ').map(Number);
    const k = parseInt(lines[2]);

    console.log(getAns(arr, n, k));
});

function getAns(arr, n, k) {
    const q = [];
    const dp = new Array(n).fill(0);
    dp[0] = arr[0];
    q.push([0, dp[0]]);

    for (let i = 1; i < n; i++) {
        // 移除窗口范围之外的元素
        while (q.length > 0 && q[0][0] < i - k) {
            q.shift();
        }

        // 计算dp[i]，取队列中的最大值加上当前元素的值
        dp[i] = arr[i] + q[0][1];

        // 移除队列中小于等于dp[i]的元素
        while (q.length > 0 && q[q.length - 1][1] <= dp[i]) {
            q.pop();
        }

        // 将当前dp[i]加入队列中
        q.push([i, dp[i]]);
    }

    return dp[n - 1];
}

题目描述

小明和朋友们一起玩跳格子游戏，每个格子上有特定的分数score[] =[1 -1-6 7 -17 7]，从起点score[0开始，每次最大的步长为k，请你返回小明跳到终点score[n-1]时，能得到的最大得分。

注:

格子的总长度和步长的区间在[1，100000]

每个格子的分数在[-10000,10000]区间中

输入描述

6 //第一行输入总的格子数量

1 -1 -6 7 -17 7/第二行输入每个格子的分数score[]

2 //第三行输入最大跳的步长k

样例1

输入

6
1 -1 -6 7 -17 7
2

输出

14