小 K 又在做白日梦了。他进入到他的幻想中发现他打下了一片江山。小 K 打下的江山一共有 n个城市城市 i和城市 i+1有一条双向高速公路连接走这条路要耗费时间 ai。小 K 为了关心人民生活决定定期进行走访。他每一次会从 1号城市到 n号城市并在经过的城市进行访问。其中终点必须为城市n。不仅如此他还有一个传送器传送半径为 k也就是可以传送到 i-k和 i+k。如果目标城市编号小于 1则为 1大于

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<int> a(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    vector<int> dp(n+1, INT_MAX);
    dp[1] = 0;
    
    for (int i = 2; i <= n; i++) {
        for (int j = max(1, i-k); j < i; j++) {
            dp[i] = min(dp[i], dp[j] + a[i]);
        }
    }
    
    cout << dp[n] << endl;
    
    return 0;
}

该程序首先读取输入的城市数量 n 和传送器半径 k。然后使用一个数组 a 来存储每个城市之间的耗时。接下来，使用动态规划的思想来计算最快的时间。

定义一个数组 dp，其中 dp[i] 表示从城市 1 到城市 i 的最快时间。初始化 dp[1] 为 0，表示从城市 1 到城市 1 的时间为 0。

接下来，从城市 2 开始，对于每个城市 i，计算 dp[i] 的值。dp[i] 的值可以通过 dp[j] + a[i] 来计算，其中 j 可以是任意小于 i 的城市，并且满足 j >= i-k。这表示从城市 j 到城市 i 的时间为 a[i]，而 dp[j] 表示从城市 1 到城市 j 的最快时间。因此，dp[i] 可以取所有符合条件的 dp[j] + a[i] 的最小值。

最后，输出 dp[n]，即从城市 1 到城市 n 的最快时间