李大志的白日梦c++

Question

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++）

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 你可以看下这个问题的回答https://ask.csdn.net/questions/660353
• 以下回答由chatgpt基于相关博客总结生成:

  这个问题可以用动态规划来解决。我会给出具体的解决方案并展示代码。

  首先，我们可以定义一个动态规划数组dp，dp[i]表示到达第i个城市所需的最快时间。

  然后，我们可以初始化dp数组。起点是1号城市，所以dp[1]为0。其它城市的最快时间初始化为一个很大的数，比如INT_MAX。

  接下来，我们可以使用一个循环来遍历所有的城市，计算dp数组的值。在计算dp[i]时，我们需要考虑以下几种情况：

  1. 如果城市i和i+1之间有一条路，那么到达城市i+1的最快时间就是到达城市i的最快时间加上走这条路的耗时。即dp[i+1] = dp[i] + a[i]。

  2. 如果城市i和i-1之间有一条路，那么到达城市i-1的最快时间就是到达城市i的最快时间加上走这条路的耗时。即dp[i-1] = dp[i] + a[i-1]。

  3. 如果传送器可以用，且传送的城市编号在有效范围内，那么到达传送城市的最快时间就是到达城市i的最快时间。

     • 如果传送的城市编号小于1，则为1。
     • 如果传送的城市编号大于n，则为n。

  最后，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和每条公路的耗时，即可得到最快结束旅行所需的时间。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^