题面描述:

维修工需要为 $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 math
import sys

def main():
    import sys
    import math

    # 读取输入
    n, k = map(int, input().split())
    x, y = map(int, input().split())

    # 初始化客户列表，索引从1到n，根据优先级排序
    p = [None] * (n + 1)  # p[0] 不使用
    for _ in range(n):
        a, b, l = map(int, sys.stdin.readline().split())
        p[l] = (a, b)  # 根据优先级 l 存储坐标

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

    INF = float('inf')
    # 初始化动态规划数组，f[i] 表示前 i 个客户的最短总距离
    f = [INF] * (n + 1)
    f[0] = 0.0  # 起点为公司，距离为0

    # 动态规划计算最短距离
    for i in range(1, n + 1):
        # 从公司到第i个客户的距离
        value = calc((x, y), p[i])
        # 往前看最多 k 个客户
        for j in range(i, max(i - k, 0), -1):
            if j < i:
                # 累加从第j个客户到第j+1个客户的距离
                value += calc(p[j], p[j + 1])
            # 更新 f[i]，选择最小的总距离
            # 总距离 = 前 j-1 个客户的最短距离 + 从公司到第j个客户的距离 + 当前批次的距离
            f[i] = min(f[i], f[j - 1] + calc((x, y), p[j]) + value)
    
    # 输出结果，保留一位小数
    print(f"{f[n]:.1f}")

if __name__ == "__main__":
    main()

题目内容

维修工要给$n$个客户更换设备，为每个用户更换一个设备。维修工背包内最多装$k$个设备，如果背包里有设备可以直接前往下一个客户更换或回公司补充设备，没有则需要回公司取设备。

这些客户有优先级，维修工需要按照优先级给客户更换设备，优先级$level$用数字表示，数字小的优先级高。

维修工从公司出发，给$n$个客户更换设备，最后再返回公司。

请计算维修工完成这项工作所需要经历的最短总距离是多少。维修工可以走斜线，请参考样例$1$图示。

输入描述

第一行两个正整数$n,k(1≤k≤n≤2000)$,表示客户数和维修工背包容量。

第二行两个正整数$x,y$，用空格分隔$(1≤x,y≤10^6)$,表示公司的坐标

接下来$n$行每行三个正整数$x_i,y_i,level_i$，用空格分隔,

$(1≤x_i,y_i≤10^6,1≤level_i≤n)$.$(x_i,y_i)$表示第$i$个客户的位置坐标$level_i$表示第$i$个客户的优先级，保证所有客户优先级不同，客户和公司坐标不会重叠，

输出描述

输出最短总距离，结果四舍五入并保留一位小数，例如:$9.0$。

样例1

输入

3 2
1 1
3 1 1
1 2 2
3 2 3

输出

9.2

解释

箭头为最短距离的规划路径:公司 -> 1 -> 公司 -> 2 -> 3 -> 公司

样例2

输入

4 1
2 2
1 1 1
1 3 4
3 1 2
3 3 3

输出

11.3

解释

维修工背包容量是$1$，逐个按优先级为每个客户更换设备，到每个客户单程距离计算为$\sqrt{2}$，往返一个客户距离是$2\sqrt{2}$，总路程为$8\sqrt{2}$ ，最短总距离四会五入后为$11.3$。