首页 > 试题广场 >

空间跃迁

[编程题]空间跃迁

热度指数：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$ 号城市的最小总耗时。

输入描述:

一行整数  . 
一行  个整数  。

输出描述:

输出一个整数，表示最小总耗时。

示例1

输入

7 0
1 1 4 5 1 4

输出

示例2

输入

7 1
1 1 4 5 1 4

输出

说明

使用空间跃迁从第  个城市跃迁到  个城市。

算法知识视频讲解

C++

牛客207135092号

#include <ios>

#include <iostream>

#include <vector>

using namespace std;

#define int long long

signed main() {

ios_base::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

int n,k;

cin>>n>>k;

vector<int> a(n,0);

vector<int> sum(n,0);

for(int i=1;i<=n-1;i++){

cin>>a[i];

sum[i]=sum[i-1]+a[i];

}

if(k>=n-1){

cout<<0;

return 0;

}

int mx=0;

for(int i=1;i<=n-1-k;i++){

int t=sum[i+k]-sum[i];

mx=max(mx,t);

}

cout<<sum[n-1]-mx;

return 0;

}

// 64 位输出请用 printf("%lld")