Background
Special for beginners, ^_^
Description
李大志做了一个白日梦。
一共有n个城市，编号为1,2,3,…n。城市 i和城市i+1有一条双向高速公路连接，走这条路要耗费时间a i。
他现在要去旅游，起点 1号城市，终点是n城市，i号城市只能到达 i+1和i−1号城市。
不仅如此，他还有一个传送器，传送距离为k，也就是可以从i城市传送到i−k或i+k号城市。如果传送的城市编号小于1则为1，大于n则为n。
但是他的传送器电量不足，只能传送一次，同时由于他出门的时候忘记关门了，他想尽快的结束，于是就想问你结束最快的时间是多少。
注意：他不必访问所有的城市，使用传送器不耗费时间
Format
Input
两行，第一行两个正整数
n,k(1≤n≤1000000,0≤k<n)。
第二行n−1个整数，第i个表示
(a i≤10000000)。
Output
一个整数，表示答案。
Samples
輸入資料 1
4 0
1 2 3
輸出資料 1
6
輸入資料 2
4 1
1 2 3
輸出資料 2
3
Limitation
1s, 1024KiB for each test case.
能给我一下思路吗？（c++）
这个问题可以用动态规划来解决。我会给出具体的解决方案并展示代码。
首先，我们可以定义一个动态规划数组dp，dp[i]表示到达第i个城市所需的最快时间。
然后，我们可以初始化dp数组。起点是1号城市，所以dp[1]为0。其它城市的最快时间初始化为一个很大的数，比如INT_MAX。
接下来，我们可以使用一个循环来遍历所有的城市，计算dp数组的值。在计算dp[i]时，我们需要考虑以下几种情况：
如果城市i和i+1之间有一条路，那么到达城市i+1的最快时间就是到达城市i的最快时间加上走这条路的耗时。即dp[i+1] = dp[i] + a[i]。
如果城市i和i-1之间有一条路，那么到达城市i-1的最快时间就是到达城市i的最快时间加上走这条路的耗时。即dp[i-1] = dp[i] + a[i-1]。
如果传送器可以用，且传送的城市编号在有效范围内，那么到达传送城市的最快时间就是到达城市i的最快时间。
最后，dp[n]就是最快结束旅行所需的时间。
以下是具体的代码实现：
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n-1);
for (int i = 0; i < n-1; i++) {
cin >> a[i];
}
vector<int> dp(n+1, INT_MAX); // 初始化dp数组，初始值为INT_MAX
dp[1] = 0; // 起点城市的最快时间为0
for (int i = 1; i <= n; i++) {
if (i+1 <= n) {
dp[i+1] = min(dp[i+1], dp[i] + a[i-1]); // 到达城市i+1的最快时间
}
if (i-1 >= 1) {
dp[i-1] = min(dp[i-1], dp[i] + a[i-2]); // 到达城市i-1的最快时间
}
if (k > 0) {
int teleport = i + k; // 传送的城市编号
teleport = min(teleport, n); // 如果传送的城市编号大于n，则为n
dp[teleport] = min(dp[teleport], dp[i]); // 到达传送城市的最快时间
}
}
cout << dp[n] << endl; // 输出最快结束旅行所需的时间
return 0;
}
你可以将上述代码复制到IDE中进行编译和运行，然后输入每组测试数据的n，k和每条公路的耗时，即可得到最快结束旅行所需的时间。
这题可以试试贪心，你找找贪心策略，或者暴力枚举