题目思路

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

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

初始值 $dp_1= 0$

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

题目内容

河面上漂浮着一排共 $n$ 个石台，依次编号为 $1$ 到 $n$ ，每个石台有一个离水面的高度 $h_i$ 。你需要从第 $1$ 个石台出发，最终到达第 $n$ 个石台。

你的跳跃能力有限：每次只能向前移动 $1$ 到 $k$ 个石台。若从石台 $i$ 跳到石台 $j$ （ $i < j \le i+k$ ），消耗的体力为 $\max(0,\, h_j - h_i)$ ，即只有当目标石台更高时才会消耗等于高度差的体力，否则体力消耗为 $0$ 。

请计算从第一个石台到最后一个石台所需的最小体力总和。

石台数量 $n$ 与最大跳跃跨度 $k$ 满足 $1 \le k \le n \le 4000$ 。