题面描述:

维修工需要为 $n$ 个客户更换设备，每个客户需要更换一个设备。维修工的背包最多可以装 $k$ 个设备，若背包里有设备则可以直接前往下一个客户更换，否则需返回公司取设备。每个客户有一个优先级，数字越小表示优先级越高，维修工必须按照优先级为客户更换设备，最后再返回公司。输入包含公司的坐标和客户的坐标及优先级，要求计算维修工完成工作所需的最短总距离，并输出结果，四舍五入保留一位小数，例如 $9.0$。

思路：动态规划/记忆化搜索

由于可以走斜线，因此无论当前处于哪一个点，接下来要去哪一个点，都可以直接计算出开销。

定义$f[i]$表示处理完第$i$个客户并回到起始点的最小开销。从$i$回去起始点$(x,y)$的开销定义为$cost$，由于我们最多持有$k$个装备，因此这$k$个装备最多分配给前$k$个客户，所以状态的转移也需要从前$k$个状态中进行。

因此有$f[i]=min(f[i], cost+dist[(x,y)->p_j]+f[j-1])$，即我们在执行完第$p_{j-1}$个客户的分配后回起始点取了一次装备，并连续完成了之后若干个客户（到第$i$个客户为止）的分配。

题解

本题的核心在于利用动态规划来计算维修工为客户更换设备所需的最短总距离。我们定义一个数组 f[i]，表示在处理完第 $i$ 个客户后返回公司所需的最小开销。具体的动态规划思路如下：

1. 距离计算

我们首先需要定义一个函数 calc，该函数用于计算两点之间的欧几里得距离。通过使用勾股定理，我们可以直接计算公司位置与客户位置之间的直线距离。这是因为维修工可以走斜线，从而无论当前处于何处，下一步的移动成本都可以被准确计算。

2. 遍历客户

在动态规划过程中，我们遍历每个客户 i，并且对于每个客户 i，我们再往回查看最多 $k$ 个客户的状态 j。如果 i 和 j 之间的客户数量超过 $k$，我们就停止该轮循环，因为超过 $k$ 的客户无法在一次出行中完成。

在遍历中，我们需要不断更新 f[i] 的值，这样能确保在处理完第 $i$ 个客户后返回公司所需的最短距离被准确记录。

3. 初始化和输出

在初始化阶段，我们将 f[0] 设置为 0，表示在没有处理任何客户时，返回公司的开销为零。最后，我们输出 f[n]，即处理完所有客户并返回公司所需的最短距离，结果格式化为保留一位小数。

代码

java

import java.util.*;

public class Main {

    static final long INF = (long) 1e15;

    // 计算两点之间的距离
    static double calc(int[] a, int[] b) {
        return Math.sqrt(Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2));
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt(); // 读取 n 的值
        int k = scanner.nextInt(); // 读取 k 的值
        int x = scanner.nextInt(); // 读取公司位置 x 坐标
        int y = scanner.nextInt(); // 读取公司位置 y 坐标

        int[][] p = new int[n + 1][2]; // 用于存储客户点的坐标

        for (int i = 1; i <= n; ++i) {
            int a = scanner.nextInt(); // 读取客户点 x 坐标
            int b = scanner.nextInt(); // 读取客户点 y 坐标
            int l = scanner.nextInt(); // 读取客户点的顺序编号
            p[l][0] = a; // 保存客户点 x 坐标
            p[l][1] = b; // 保存客户点 y 坐标
        }

        double[] f = new double[n + 1]; // 用于存储从公司到第i个点的最短时间
        Arrays.fill(f, INF); // 将数组初始化为无穷大
        f[0] = 0; // 初始化从公司出发的时间为0

        // 动态规划
        for (int i = 1; i <= n; ++i) {
            // 计算从公司到第i个点的距离
            double value = calc(new int[]{x, y}, p[i]);
            
            // 往前看k个客户点
            for (int j = i; j > 0; --j) {
                if (i - j + 1 > k) {
                    break;
                }
                // 如果j < i , 计算从第j个点到j+1个点的距离
                // 也就是更新在路上的时间
                if (j < i) {
                    value += calc(p[j], p[j + 1]);
                }
                // 更新f[i] , 也就是从公司到第i个点的最短时间
                // 具体的, 就是从公司到第j个点的时间 + 从第j个点到第i个点的时间 + 从最开始到第j个点的最短时间
                f[i] = Math.min(f[i], value + calc(new int[]{x, y}, p[j]) + f[j - 1]);
            }
        }

        System.out.printf("%.1f%n", f[n]); // 输出从公司到第n个点的最短时间，并保留一位小数
    }
}

C++

#include <iostream>
#include <cmath>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;

const long long INF = 1e15;

// 计算两点之间的距离
double calc(pair<int, int> a, pair<int, int> b) {
    return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}

int main() {
    int n, k;
    cin >> n >> k;
    
    int x, y;
    cin >> x >> y;

    vector<pair<int, int>> p(n + 1);
    for (int i = 1; i <= n; ++i) {
        int a, b, l;
        cin >> a >> b >> l;
        p[l] = {a, b}; // 将坐标存储在对应的顺序位置上
    }

    vector<double> f(n + 1, INF);
    f[0] = 0;

    // 动态规划
    for (int i = 1; i <= n; ++i) {
        // 计算从公司到第i个点的距离
        double value = calc({x, y}, p[i]);
        
        // 往前看k个客户点
        for (int j = i; j > 0; --j) {
            if (i - j + 1 > k) {
                break;
            }
            // 如果j < i , 计算从第j个点到j+1个点的距离
            // 也就是更新在路上的时间
            if (j < i) {
                value += calc(p[j], p[j + 1]);
            }
            // 更新f[i] , 也就是从公司到第i个点的最短时间
            // 具体的, 就是从公司到第j个点的时间 + 从第j个点到第i个点的时间 + 从最开始到第j个点的最短时间
            f[i] = min(f[i], value + calc({x, y}, p[j]) + f[j - 1]);
        }
    }

    cout << fixed << setprecision(1) << f[n] << endl;

    return 0;
}

python

import sys
import math
# 计算两点之间的距离
def calc(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

n , k = map(int , input().split())
x , y = map(int , input().split())

p = [None] * (n + 1)
for i in range(1, n + 1):
    a , b , l = map(int , input().split())
    p[l] = (a, b)


f = [10**15] * (n + 1)
f[0] = 0
# 动态规划
for i in range(1, n + 1):
    # 计算从公司到第i个点的距离
    value = calc((x, y), p[i])
    # 往前看k个客户点
    for j in range(i, 0, -1):
        if i - j + 1 > k:
            break
        # 如果j < i , 计算从第j个点到j+1个点的距离
        # 也就是更新在路上的时间
        if j < i:
            value += calc(p[j], p[j + 1])
        # 更新f[i] , 也就是从公司到第i个点的最短时间
        # 具体的, 就是从公司到第j个点的时间 + 从第j个点到第i个点的时间+ 从最开始到第j个点的最短时间
        f[i] = min(f[i], value + calc((x, y), p[j]) + f[j - 1])

print(f"{f[n]:.1f}")

竟然没有卡我的精度…

#include<bits/stdc++.h>
using namespace std;
struct STU{
	int x,y,id;
}stu[2020];
int N,K,X,Y;
const int inf=1e9+7;
bool cmp(const STU&a,const STU&b){
	return a.id<b.id;
}
double dp[2020][2020];
double dis(int a,int b){
	double t=(stu[a].x-stu[b].x)*(stu[a].x-stu[b].x);
	t+=(stu[a].y-stu[b].y)*(stu[a].y-stu[b].y);
	t=sqrt(t);
	return t;
}
int main(){
	cin>>N>>K;
	cin>>X>>Y;
	for(int i=1;i<=N;i++){
		cin>>stu[i].x>>stu[i].y>>stu[i].id;
	}
	sort(stu+1,stu+N+1,cmp);
	for(int i=0;i<=N;i++)
		for(int j=0;j<=K;j++)dp[i][j]=inf;
	for(int j=0;j<=K;j++)dp[0][j]=0;
	stu[0].x=X; stu[0].y=Y;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=K;j++){
			if(j!=K){
				dp[i][j]=min(dp[i][j],dp[i-1][j+1]+dis(i-1,i));
			}
			dp[i][K]=min(dp[i][K],dp[i-1][j]+dis(i-1,0)+dis(0,i));
		}
	}
	double ans=inf;
	for(int j=1;j<=K;j++)
		ans=min(ans,dp[N][j]);
	ans=ans+dis(N,0);
	printf("%.1lf",ans);
	return 0;
}