分数: 466 分
问题陈述
高桥正试图过河。有 N 踏脚石在河里排成一排,编号石 1,石头 2, \ldots,石头 N 从左岸开始依次排列。高桥从石头开始 1 当他到达石头时就达到了目标 N.
来自他现在的石头 i,高桥可以跳到任意一块石头上 i+1,石头 i+2, \ldots,石头 \min(i+K,\, N)。换句话说,单次跳跃所覆盖的石头数量之差为 1 和 K 包容,他只能向数字增加的方向移动。高桥必须准确落在石头上 N 最后。
每块垫脚石 i (1 \leq i \leq N) 具有正整数值 A_i 分配给它。当高桥落在一块石头上时,该石头的价值就会添加到累计成本中。他没有落在的石头的价值不会被添加。价值 A_1 起始石 1 和值 球门石的 A_N 当他降落在它们上时,也会添加 N 。
高桥可以从石头上走的所有路径中 1 去石头 N,找到使累积成本最小的一个,并输出最小的累积成本。
约束
- 2 \leq N \leq 10^6
- 1 \leq K \leq N - 1
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数。
输入
N K A_1 A_2 \ldots A_N
- 第一行包含一个整数 N 代表垫脚石的数量和一个整数 K 代表单次跳跃可以覆盖的石头数量的最大差异,以空格分隔。
- 第二行包含整数 A_1, A_2, \ldots, A_N 代表每个踏脚石的值,以空格分隔。
输出
一行输出从石头出发时的最小累积成本 1 去石头 N.
示例输入 1
5 2 1 3 2 4 1
示例输出 1
4
示例输入 2
6 3 10 1 1 1 1 10
示例输出 2
21
示例输入 3
10 3 5 8 3 7 2 9 1 6 4 3
示例输出 3
14
示例输入 4
20 4 3 9 1 8 2 7 4 6 5 10 1 3 8 2 7 5 9 1 6 4
示例输出 4
16
示例输入 5
2 1 1000000000 1000000000
示例输出 5
2000000000