跳格子3 - 华为OD统一考试(C卷)

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

小明和朋友们一起玩跳格子游戏，每个格子上有特定的分数，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

输出描述

14 // 输出最大得分数，小明从起点score[0]开始跳，第一次跳score[1], 第二次跳到score[3],第三次跳到score[5]，因此得到的最大的得分是score[0] + score[1] + score[3] + score[5] = 14

示例1

输入：
6
1 -1 -6 7 -17 7
2

输出：
14

题解

题目类型： 动态规划问题，使用优先级队列来优化。

解题思路： 动态规划问题，定义状态和状态转移方程。使用优先级队列（大根堆）来维护前面格子已经获得的最大得分，保证每次选择最大得分的格子进行跳跃。

代码大致描述：

输入格子数量 n，每个格子的分数 scores，以及最大跳步长 k。
初始化优先级队列 pq，用于存储 (得分, 位置) 对，根据得分从大到小排序。
初始化 dp 数组，dp[i] 表示跳到位置 i 时可以获得的最大得分。
遍历格子，计算每个位置的最大得分，并使用优先级队列维护前面格子的最大得分信息。
输出 dp 数组的最后一个元素，即到达终点时的最大得分。

时间复杂度： O(n log n)，其中 n 为格子的数量。因为在每一步都需要操作优先级队列，插入和删除的时间复杂度为 O(log n)。

空间复杂度： O(n)，用于存储 dp 数组和优先级队列。

Java

import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        int[] scores = new int[n];
        for (int i = 0; i < n; i++) scores[i] = in.nextInt();

        // 最大步长
        int k = in.nextInt();

        // 优先级队列用于维护前面格子已经获得的最大得分
        // 存储格式 {得分, 位置}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a1, a2) -> a2[0] - a1[0]);

        // dp[i] 表示跳到 i 可以能得到的最大得分
        int[] dp = new int[n];
        dp[0] = scores[0];
        pq.offer(new int[]{dp[0], 0});
		
        // 遍历数组，计算每个位置的最大得分
        for (int i = 1; i < n; i++) {
            // 不能从  pq.peek()[1] 步跳到 i，因此抛弃
            while (!pq.isEmpty() && i - pq.peek()[1] > k) pq.poll();
			
            // 计算当前位置的最大得分
            dp[i] = pq.peek()[0] + scores[i];
            pq.offer(new int[]{dp[i], i});
        }

        System.out.println(dp[n - 1]);
    }
}

Python

import heapq

# 主函数
def main():
    # 输入 n
    n = int(input())
    
    # 输入各个位置的得分
    scores = list(map(int, input().split()))

    # 输入最大步长 k
    k = int(input())

    # 使用大根堆来存储 (得分, 位置) 对
    pq = []
    
    # dp[i] 表示跳到 i 可以能得到的最大得分
    dp = [0] * n
    dp[0] = scores[0]
    
    # 将第一个位置的得分和位置加入最大堆
    heapq.heappush(pq, (-dp[0], 0))

    # 遍历数组，计算每个位置的最大得分
    for i in range(1, n):
        # 不能从 pq[0][1] 步跳到 i，因此抛弃
        while pq and i - pq[0][1] > k:
            heapq.heappop(pq)

        # 计算当前位置的最大得分
        dp[i] = -pq[0][0] + scores[i]
        
        # 将当前位置的得分和位置加入最大堆
        heapq.heappush(pq, (-(dp[i]), i))

    # 输出最后一个位置的最大得分
    print(dp[n - 1])

# 调用主函数
if __name__ == "__main__":
    main()

C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    cin >> n;
    vector<int> scores(n);
    for(size_t i = 0; i < n; i++) cin >> scores[i];

    // 最大步长
    cin >> k;

    priority_queue<pair<int, int>> pq;
    // dp[i] 表示跳到 i 可以能得到的最大得分
    vector<int> dp(n, 0);
    dp[0] = scores[0];
    pq.push({dp[0], 0});

    for(size_t i = 1; i < n; i++){
        // 不能从  pq.top().second 步跳到 i，因此抛弃
        while(!pq.empty() && i - pq.top().second > k) pq.pop();

        dp[i] = pq.top().first + scores[i];
        pq.push({dp[i], i});
    }

    cout << dp[n - 1] << endl;
    
    return 0;
}