直接dfs java版

import java.util.Scanner;

public class Main {
    static int[] ns;
    static int b,k;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        k = in.nextInt();
         ns = new int[n];
        for (int i = 0; i < n; i++) {
            ns[i]=in.nextInt();
        }
        b = in.nextInt();
        int m = in.nextInt();
        System.out.println(dfs(n,0,m));
    }

    public static int dfs(int index, int count, int leftSubway){
        if (index==0){
            return count;
        }
        if (leftSubway==0){
            return dfs(index-1,count+ns[index-1],0);
        }else{
            int noS = dfs(index-1,count+ns[index-1],leftSubway);
            for (int i = 1; i <= k; i++) {
                noS = Math.min(dfs(Math.max(0,index-i),count+b*(Math.min(i,index)),leftSubway-1),noS);
            }
            return noS;
        }
    }
}

数据量很小，爆搜

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int metro_cost, metro_count;
int n, metro_blocks_count;
int ans = INT_MAX;
int curr_cost = 0;
int curr_metro = 0;

void dfs(vector<int>& walk_time, int start) {
	if (start == n) {
		ans = min(ans, curr_cost);
		return;
	}

	if (walk_time[start] < metro_cost || curr_metro == metro_count) {
		curr_cost += walk_time[start];
		dfs(walk_time, start + 1);
		curr_cost -= walk_time[start];
	}
	else {
		if (curr_metro < metro_count) {
			for (int i = start; i < min(n, start + metro_blocks_count); ++i) {
				curr_cost += (i - start + 1) * metro_cost;
				++curr_metro;
				dfs(walk_time, i + 1);
				curr_cost -= (i - start + 1) * metro_cost;
				--curr_metro;
			}
		}

		curr_cost += walk_time[start];
		dfs(walk_time, start + 1);
		curr_cost -= walk_time[start];
	}


}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> metro_blocks_count;
	vector<int> walk_time(n);
	for (int i = 0; i < n; ++i) {
		cin >> walk_time[i];
	}
	cin >> metro_cost >> metro_count;

	dfs(walk_time, 0);

	cout << ans << endl;
}
```
`

题意化简

这个题的本质是一个路径规划问题。你有n个街区，每个街区有步行时间a_i，可以选择步行一格或乘坐地铁跳跃1到K个街区，地铁每格花费B时间。你最多可以坐M次地铁，目标是找到从第1个街区到第N个街区的最小时间消耗。

思路

  此题是一个经典的动态规划问题，设置dp[i][j]为走到第i个街区并且已经坐了j次地铁的最短时间，转移则分为两种情况，一种是从前一个位置到当前位置不做地铁，一种是坐地铁到当前位置，第二种情况要枚举从前方哪里坐的地铁到现在的位置，并取最小值，初始化则为全不坐地铁的情况

题解

这道题是一个经典的动态规划问题。我们可以将城市的街区视为一个线性序列，使用动态规划来求解从第一个街区到最后一个街区的最短时间。定义动态规划状态 dp[i][j] 表示走到第 i 个街区，并且已经坐了 j 次地铁的最短时间。

动态规划思路

1. 状态定义：

   • dp[i][j]：表示走到第 i 个街区，并且使用了 j 次地铁的最小时间。

2. 初始化：

   • dp[0][0] = 0：表示在城市的起点（第0个位置，左侧）时，不需要任何时间。
   • dp[i][0]：仅通过步行到达第 i 个街区的时间，可以通过前一个街区的时间累加步行所需的时间。

3. 状态转移：

   • 对于每一个街区 i：
     • 不坐地铁：从 i-1 走到 i，时间为 dp[i-1][j] + a[i]。
     • 坐地铁：从前面的某个街区 l 坐地铁到当前街区 i。这里我们需要枚举所有可能的前一个街区 l，l 必须在 i - k 和 i - 1 之间，以确保我们不超过地铁的最大跨越数量 k。
     • 每次坐地铁的时间为 b * (i - l)。

4. 最终结果：

   • 结果为 dp[n][j] 中的最小值，j 可以从 0 到 m，表示我们使用的地铁次数。

代码说明

1. 常数定义：使用 const long long inf = 1e18; 来表示一个无穷大，便于后续的最小值比较。
2. 输入部分：读取街区数量 n、地铁一次最多可跨越的街区数 k、每个街区的步行时间以及地铁的时间 b 和最多可坐地铁的次数 m。
3. 动态规划数组：dp 数组初始化为无穷大，只有起始位置 dp[0][0] 被初始化为0。
4. 动态规划计算：根据状态转移方程更新 dp 数组的值。
5. 输出结果：在所有使用0到 m 次地铁的情况下，输出最小时间。

代码

c++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const long long inf = 1e18;  // 定义一个足够大的常数，表示无穷大

int main() {
    int n, k, m;  // n为街区数量，k为地铁一次最多可跨越的街区数，m为最多可坐地铁次数
    cin >> n >> k;
    
    vector<int> a(n + 1);  // 保存每个街区的步行时间，从1开始
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    
    int b;  // 每次坐地铁的时间
    cin >> b >> m;

    // 初始化dp数组，dp[i][j] 表示到达第 i 个街区使用 j 次地铁的最小时间
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, inf));
    dp[0][0] = 0;  // 起点不花时间

    // 动态规划过程
    for (int i = 1; i <= n; ++i) {
        // 仅通过步行到达第 i 个街区的时间
        dp[i][0] = dp[i - 1][0] + a[i];
        
        for (int j = 1; j <= m; ++j) {  // 0到m次地铁
            // 不坐地铁的情况
            dp[i][j] = dp[i - 1][j] + a[i];
            
            // 坐地铁的情况，枚举从前面哪个街区坐地铁
            int last = max(0, i - k);  // 可以坐地铁的最远起始点
            for (int l = last; l < i; ++l) {  // l是前一个街区的索引
                // 更新使用 j 次地铁的最小时间
                dp[i][j] = min(dp[i][j], dp[l][j - 1] + b * (i - l));
            }
        }
    }

    // 输出最小结果
    long long result = inf;  // 初始化结果为无穷大
    for (int j = 0; j <= m; ++j) {
        result = min(result, dp[n][j]);  // 取到达第 n 个街区的最小时间
    }
    
    cout << result << endl;  // 输出最终结果
    return 0;
}

python

n = int(input())
k = int(input())
a = [0] + list(map(int, input().split()))
b = int(input())
m = int(input())
inf = 10**18
dp = [[inf] * (m + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1 , n + 1):
    dp[i][0] = dp[i - 1][0] + a[i]
    for j in range(1 , m + 1):
        dp[i][j] = dp[i - 1][j] + a[i]
        # 坐地铁，最远坐k站，枚举到底要坐多少站
        last = max(0 , i - k)
        for l in range(last , i):
            dp[i][j] = min(dp[i][j] , dp[l][j - 1] + b * (i - l))
print(min(dp[n]))

java

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }
        int b = sc.nextInt();
        int m = sc.nextInt();
        
        long inf = (long) 1e18;
        long[][] dp = new long[n + 1][m + 1];
        
        // 初始化 dp 数组
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], inf);
        }
        dp[0][0] = 0;
        
        // 动态规划过程
        for (int i = 1; i <= n; i++) {
            dp[i][0] = dp[i - 1][0] + a[i];  // 不坐地铁
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i - 1][j] + a[i];  // 不坐地铁
                int last = Math.max(0, i - k);
                for (int l = last; l < i; l++) {  // 坐地铁，最远坐k站，枚举到底要坐多少站
                    dp[i][j] = Math.min(dp[i][j], dp[l][j - 1] + b * (i - l));
                }
            }
        }
        
        // 输出最小结果
        long result = inf;
        for (int j = 0; j <= m; j++) {
            result = Math.min(result, dp[n][j]);
        }
        System.out.println(result);
    }
}

n = int(input())
k = int(input())
a = [0]+list(map(int,input().split()))
B = int(input())
M = int(input())
inf = 10**18
dp = [[inf]*(M+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
    dp[i][0] = dp[i-1][0]+a[i]
    for j in range(1,M+1):
        dp[i][j] = dp[i-1][j]+a[i]
        last = max(0,i-k)
        for l in range(last,i):
            dp[i][j] = min(dp[i][j],dp[l][j-1]+B*(i-l))
print(min(dp[n][j] for j in range(M+1)))

private static void city(int[] blocks, int n, int k, int b, int m){
        int[][] dp = new int[n + 1][m + 1];
        for(int i = 1; i <= n; i++){
            //dp[0]为不做地铁的情况
            dp[i][0] = dp[i - 1][0] + blocks[i - 1];
            //从做一次地铁开始遍历
            //可以不用考虑徒步穿越花销小于地铁的情况，因为我们只考虑最小值
            for(int j = 1; j <= m; j++){
                //考虑坐地铁的情况，要么本次坐，要么本次不坐
                //这个是本次不坐地铁的花销
                dp[i][j] = dp[i - 1][j] + blocks[i - 1];
                //计算连续回溯值时考虑index小于0的情况
                int track = Math.max(1, i - k + 1);
                //从i开始回溯到最远点
                for(int s = i; s >= track; s--){
                    //本次坐地铁
                    int subway = dp[s - 1][j - 1] + b * (i - s + 1);
                    //这里dp[i][j]和subway的时间对比，取较小值，可以有效排除 步行1分钟，地铁3分钟 的情况
                    //dp[i][j]的含义是本次不坐地铁，前面做了j次地铁
                    //subway是本次坐地铁，如果步行小于地铁时间，则取dp[i][j]
                    dp[i][j] = Math.min(dp[i][j], subway);
                }
            }
        }
        System.out.println(dp[n][m]);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextInt()){
            int n = in.nextInt();
            int k = in.nextInt();
            int[] blocks = new int[n];
            for(int i = 0; i < n; i++){
                blocks[i] = in.nextInt();
            }
            int b = in.nextInt();
            int m = in.nextInt();
            city(blocks, n, k, b, m);
        }
    }