首页 > 试题广场 >

空间跃迁

[编程题]空间跃迁
  • 热度指数：42 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}有 n 个城市排成一列，城市 i 与 i+1 之间行走耗时 a_i。旺仔哥哥想要从 1 号城市出发到 n 号城市，可在任意时刻使用一次空间跃迁，半径为 k，即可以从第 i 个城市无时间消耗地传送至第 \max\{0,i-k\} 或第 \min \{ n,i+k\} 个城市。求旺仔哥哥从 1 号城市出发到 n 号城市的最小总耗时。

输入描述:
\hspace{15pt}一行整数 n,k (2\leqq n\leqq 10^5,\ 0\leqq k < n). 
\hspace{15pt}一行 n-1 个整数 a_i (1\leqq a_i\leqq 10^9)。


输出描述:
\hspace{15pt}输出一个整数，表示最小总耗时。
示例1

输入

7 0
1 1 4 5 1 4

输出

16
示例2

输入

7 1
1 1 4 5 1 4

输出

11

说明

使用空间跃迁从第 4 个城市跃迁到 5 个城市。
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 30浏览

热门推荐

相关试题

空间跃迁

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号