题目思路

使用动态规划解决即可，即每次使用之前的计算过的状态来求出当前状态的结果，在这道题中就是用所有能到达当前所求的楼梯的花费来更新当前所求的答案，转移方程为

$dp_i = min_{j=i-k}^{j<i} (dp_{i-k}+max(0, a_i-a_j))$

初始值 $dp_1= 0$

直接将这个方程用代码实现即可，最后 $dp_n$ 即为答案

题目大意

有个神奇楼梯，每次可以传送不超过 $k$ 个楼梯，而每次爬楼花费的体力为 $max(0, 目标楼梯高度-当前楼梯高度)$ .

现在小红想知道求从第一个楼梯到最后一个楼梯的最小花费是多少。

输入描述

第一行输入$n,k$，代表楼梯的阶数和最多能传送跨过多少个楼梯。

第二行$n$个数，代表每座楼梯的高度

样例

输入

7 4
12 38 14 71 31 61 33

输出

21

数据范围

$1\le k \le n \le 4000$