← 返回题目列表

AtCoder · awc0033_e

E. 垫脚石的最低成本

中文机器翻译题面 查看原题

分数: 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