企业官网建设流程全解析

一、题目描述

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

注：
1、格子的总长度和步长的区间在[1，100000]；
2、每个格了的分数在[-10000,10000]区间中；

二、输入输出描述

输入描述

• 第一行：格子总数；
• 第二行：每个格子的分数；
• 第三行：最大步长k。

输出描述

• 一个整数，表示从起点跳到终点能获得的最大得分。

三、示例

四、解题思路

1. 核心思想

动态规划（DP）+ 单调队列优化：

• 用dp[i]表示到达i的最大得分
• 转移需要前 k 个 dp 值的最大值
• 用单调递减队列在 O (1) 时间获取窗口最大值，把复杂度从 O (nk) 优化到 O (n)

2. 问题本质分析

这是一个带窗口限制的动态规划问题：

• 状态转移：dp[i] = max(dp[i-k ... i-1]) + score[i]
• 约束：只能从前面最多 k 个位置跳过来
• 目标：求dp[n-1]（最后一格的最大得分）
• 本质：滑动窗口最大值 + DP 递推

3. 核心逻辑

1. DP 定义：dp[i]= 到达第i格的最大总分
2. DP 转移：
   • 只能从i-k~i-1跳过来
   • 取这段区间的最大 dp 值+ 当前格子分数
3. 单调队列优化：
   • 队列存下标，dp 值单调递减
   • 队首永远是窗口内最大值
   • 超出窗口、比当前值小的元素及时移除
4. 最终答案 =dp[n-1]

4. 步骤拆解

1. 输入与初始化

   • 读取格子数、分数、最大跳跃步数 k
   • 初始化 dp 数组与单调队列

2. 遍历每个格子

   • 清除队首超出跳跃范围的元素
   • 用队首最大值计算 dp [i]
   • 维护队列单调递减
   • 将当前下标加入队列

3. 输出结果

   • 输出最后一个位置的最大得分

五、代码实现

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] score = new int[n]; for (int i = 0; i < n; i++) { score[i] = sc.nextInt(); } int k = sc.nextInt(); long[] dp = new long[n]; dp[0] = score[0]; // 单调队列：存储下标，对应 dp 值递减 Deque<Integer> q = new ArrayDeque<>(); q.offer(0); for (int i = 1; i < n; i++) { // 移除窗口外的元素（超过 k 步） while (!q.isEmpty() && q.peek() < i - k) { q.poll(); } // 前面窗口最大值 + 当前分数 dp[i] = dp[q.peek()] + score[i]; // 维护队列递减：比 dp[i] 小的都没用 while (!q.isEmpty() && dp[i] >= dp[q.peekLast()]) { q.pollLast(); } q.offer(i); } System.out.println(dp[n - 1]); } }