题面描述:

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

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

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

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

题目内容

维修工要给$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$。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写