跳格子3 - 华为OD统一考试（C卷）-免费看题解

OD统一考试（C卷）
分值： 200分
题解： Java / Python / C++

题目描述

小明和朋友们一起玩跳格子游戏，

每个格子上有特定的分数 score = [1, -1, -6, 7, -17, 7]，

从起点score[0]开始，每次最大的步长为k，请你返回小明跳到终点 score[n-1] 时，能得到的最大得分。

输入描述

第一行输入总的格子数量 n

第二行输入每个格子的分数 score[i]

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

输出描述

输出最大得分

备注

格子的总长度 n 和步长 k 的区间在 [1, 100000]
每个格子的分数 score[i] 在 [-10000, 10000] 区间中

示例1

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

输出：
14

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

题解

动态规划：
创建一个数组 dp，其中 dp[i] 表示跳到 score[i] 时能得到的最大得分。
状态转移方程：dp[i] = max(dp[i-1],dp[i-2],...,dp[i-k]) + score[i];
但只是这样只能过40%的测试用例
大顶堆优化：
使用大顶堆来维护前 k 个dp 值，以便在每一步更新 dp[i] 时直接从堆顶取得最大值。
这样大概能过95%的测试用例
单调队列优化：
使用双向队列从尾部添加dp[i]的下标i，添加之前判断队列尾部的下标last对应的元素dp[last]是否比dp[i]小
dp[last]比dp[i]小，则将dp[last]取出丢弃。因为在dp[i]前面的比dp[i]还小的值不会被后面使用到，后面要的是最大值。
这样队列里保存的下标对应的dp元素是单调递减的。较小的元素直接淘汰，无需多次排序。

动态规划+大顶堆：

public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	while (in.hasNextInt()) {
		long start = System.currentTimeMillis();
		int n = in.nextInt();
		int[] arr = new int[n];// 每个格子的分数，格子最少长度为1，格子分数可以为负数
		for (int i = 0; i < n; i++) {
			arr[i] = in.nextInt();
		}
		if (arr.length == 1){
			System.out.println(arr[0]);
			continue;
		}
		int k = in.nextInt();// 最大步长，即步长为1-k之间
		int[] dp = new int[arr.length];
		PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
		for (int i = 0; i < arr.length; i++) {
			if (i==0){
				dp[i] = arr[0];
			}else {
				dp[i] = queue.peek() + arr[i];
			}
			queue.add(dp[i]);
			if (i-k>=0){
				queue.remove(dp[i-k]);
			}
		}
		System.out.println(dp[dp.length-1]);
	}
}

动态规划+单调队列：

public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	while (in.hasNextInt()) {
		int n = in.nextInt();
		int[] arr = new int[n];// 每个格子的分数，格子最少长度为1，格子分数可以为负数
		for (int i = 0; i < n; i++) {
			arr[i] = in.nextInt();
		}
		if (arr.length == 1){
			System.out.println(arr[0]);
			continue;
		}
		int k = in.nextInt();// 最大步长，即步长为1-k之间
		int[] dp = new int[arr.length];
		// 使用一个双端队列来维护单调递减的索引
		Deque<Integer> deque = new LinkedList<>();
		for (int i = 0; i < arr.length; i++) {
			// 移除队列中超出步长限制的索引
			if (!deque.isEmpty() && i - deque.peekFirst() > k) {
				deque.pollFirst();
			}
			// 更新当前位置的最大得分
			dp[i] = (deque.isEmpty() ? 0 : dp[deque.peekFirst()]) + arr[i];
			// 保持单调递减性质，比当前dp[i]还小的dp[i-x]已经没有用了，要取也是取当前dp[i]或前面更大的值
			while (!deque.isEmpty() && dp[i] >= dp[deque.peekLast()]) {
				// 队列中无用的索引移除
				deque.pollLast();
			}
			// 将当前索引加入队列
			deque.offerLast(i);
			// 对于dp数组 8 5 4 3 7 0 0，假如步长k=4，arr[4]=-1
			// i=4时队列里存的dp的索引index为 0 1 2 3，其对应的dp元素是递减的
			// 计算dp[4] = 8 + arr[4] = 7
			// 此时，dp数组中dp[1] dp[2] dp[3]都比dp[4] 小，将队列中的对应index移除
			// 最后添加当前索引i=4到队列末尾，此时队列中的index对应的dp元素还是递减的
		}
		System.out.println(dp[dp.length-1]);
	}
}