E卷-跳格子3(200分)

跳格子3

问题描述

小明和朋友们正在玩跳格子游戏。游戏中有 个格子，每个格子上有特定的分数。小明从起点（第一个格子）开始，每次最多可以跳 步。请计算小明跳到终点（最后一个格子）时能获得的最大得分。

输入格式

第一行包含一个整数 ，表示格子的总数量。

第二行包含 个整数 ，表示每个格子的分数。

第三行包含一个整数 ，表示每次跳跃的最大步长。

输出格式

输出一个整数，表示小明能获得的最大得分。

样例输入

6
1 -1 -6 7 -17 7
2

样例输出

14

样例解释

数据范围

题解

单调队列优化DP

这道题目本质上是一个动态规划问题，但需要用到单调队列来优化时间复杂度。解题思路如下：

1. 定义 dp[i] 为跳到第 i 个格子时能获得的最大得分。

2. 对于第 i 个格子，可以从前面 k 个格子中的任意一个跳过来。因此，状态转移方程为：

3. 直接计算上述方程的时间复杂度是 O(nk)，对于大规模数据会超时。这里可以使用单调队列来优化。

4. 维护一个单调递减的双端队列，队列中存储的是格子的索引。队首元素始终是当前窗口内最大值的索引。

5. 遍历每个格子时，执行以下操作：

   • 如果队首元素已经超出当前窗口范围，将其弹出。
   • 将新元素加入队尾，同时保持队列的单调性（从队尾移除所有小于当前元素的值）。
   • 队首元素即为当前窗口内的最大值。

参考代码

• Python

from collections import deque

def max_score(n, scores, k):
    # 初始化 dp 数组，dp[i] 表示到达第 i 个格子时的最大得分
    dp = [0] * n
    dp[0] = scores[0]
    
    # 初始化单调队列，存储格子的索引
    queue = deque([0])
    
    # 遍历每个格子
    for i in range(1, n):
        # 移除队列中超出窗口范围的元素
        if queue and queue[0] < i - k:
            queue.popleft()
        
        # 计算当前格子的最大得分
        dp[i] = dp[queue[0]] + scores[i]
        
        # 维护单调队列
        while queue and dp[queue[-1]] <= dp[i]:
            queue.pop()
        queue.append(i)
    
    # 返回最后一个格子的最大得分
    return dp[-1]

# 读取输入
n = int(input())
scores = list(map(int, input().split()))
k = int(input())

# 计算并输出结果
result = max_score(n, scores, k)
print(result)

• C

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100001

int dp[MAX_N];
int queue[MAX_N];
int front = 0, rear = 0;

int max_score(int n, int* scores, int k) {
    dp[0] = scores[0];
    queue[rear++] = 0;
    
    for (int i = 1; i < n; i++) {
        // 移除队列中超出窗口范围的元素
        if (front < rear && queue[front] < i - k) {
            front++;
        }
        
        // 计算当前格子的最大得分
        dp[i] = dp[queue[front]] + scores[i];
        
        // 维护单调队列
        while (front < rear && dp[queue[rear-1]] <= dp[i]) {
            rear--;
        }
        queue[rear++] = i;
    }
    
    return dp[n-1];
}

int main() {
    int n, k;
    int scores[MAX_N];
    
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &scores[i]);
    }
    scanf("%d", &k);
    
    int result = max_score