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

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

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

先学习一下单调队列

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

题目描述

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