题目内容

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

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

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

题面描述:

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

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

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

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