解题思路

思路

设当前场上的宝可梦为 $u$，下一只要雇佣的宝可梦为 $v$。若选择第 $j$ 个属性对战，只需先将 $a_{v,j}$ 增加到至少 $a_{u,j}$，这部分的最小费用是

因此从 $u$ 换到 $v$ 的最小费用为

把每只宝可梦看成一个顶点，该式就是一条从 $u$ 到 $v$ 的有向边权。答案是从第 $1$ 个顶点到第 $n$ 个顶点的最短路。所有边权非负，可用 Dijkstra 算法。

做法

子任务 1

当 $n\le 80$ 时，可以直接枚举最短路中的当前点 $u$、下一个点 $v$ 以及对战属性 $j$，不显式存储完全图。时间复杂度为 $O(n^2m)$，空间复杂度为 $O(nm)$。

满分做法

对每个属性 $j$，将所有宝可梦按 $a_{i,j}$ 从小到大排序，并为排序后的每个位置建立一个辅助顶点。

在同一个属性的排序链上：

• 从属性值较小的相邻位置走向较大的位置，边权为 $0$；
• 从较大的相邻位置走向较小的位置，边权为两个属性值之差。

每个原顶点 $u$ 向它在每条属性链中的位置连一条边权为 $0$ 的边；每个位置顶点向该位置所属的宝可梦 $v$ 连一条边权为 $c_v$ 的边。

从 $u$ 在第 $j$ 条链上的位置走到 $v$ 的位置：若 $a_{v,j}\ge a_{u,j}$，只需沿零边权方向移动；否则逆向边权望远镜式相加，总和恰为 $a_{u,j}-a_{v,j}$。再加上离开辅助顶点时的 $c_v$，正好得到选用第 $j$ 个属性的转移费用。在所有属性链中取最短路，便自动取到最优属性。

图中有 $O(nm)$ 个辅助顶点和 $O(nm)$ 条可隐式枚举的边。排序与 Dijkstra 的总时间复杂度为 $O(nm\log(nm))$，空间复杂度为 $O(nm)$。

正确性说明

对任意两只宝可梦 $u,v$ 和属性 $j$，对应排序链上从 $u$ 的位置到 $v$ 的最短距离恰为 $\max(0,a_{u,j}-a_{v,j})$。离开该位置时再支付 $c_v$，因而辅助图完整且精确地表示原问题中的每一次最优雇佣与对战。反之，辅助图的每段路径也都可对应到先增加挑战者的某一属性、再雇佣对战的合法操作。所以从顶点 $1$ 到顶点 $n$ 的最短路与原问题的最小费用完全相同。

复杂度

子任务 1 的时间复杂度为 $O(n^2m)$，空间复杂度为 $O(nm)$。满分做法的时间复杂度为 $O(nm\log(nm))$，空间复杂度为 $O(nm)$。