CF1936C Pokémon Arena 题解

LKY928261 · 2024-03-01 09:18:16 · 题解

有个较为显然的结论：

• 任意最优方案中，相邻两次 2 操作中的 j 不同。

证明：假设相邻两次操作中，先用 y 的 i 属性打败了 x，再用 z 的 i 属性打败了 y，那么直接用 z 的 i 属性打败 x 可以节省 c_y 的雇佣费，并且后者所需要提升的能力值不多于前者，即后者一定更优。

于是用 y 的 i 属性打败 x 所需提升的能力值永远是 \max(0,a_{y,i}-a_{x,i})，因为根据结论 a_{x,i} 不会在前面的操作中被修改。

先直接建出图。图上点 x 的权值为雇佣费 c_x。从点 x 向点 y 连 m 条有向边，其中第 i 条的边权为 \max(0,a_{y,i}-a_{x,i})。一条 1 到 n 的路径长度为路径上边权与除 c_1 外所有点权的总和。于是原题就转化成了一个最短路问题。

带着点权做并不方便。可以考虑将一个点拆成入点和出点，从入点向出点连权值为 c_x 的边。这样就把点权转成了边权。

直接这样做有 \Theta(n^2m) 条边，不可接受，需要优化。

将 m 个属性值分开考虑。由于 x 到 y 的边权为两者对应属性值的差，显然可以按属性值对 n 个点排序，每个点只向相邻的点连边。这样单层的边数就变成 了 \Theta(n)，一共 m 层。

简单总结一下：

• 一共有 n 个出点，以及 m 层入点，每层 n 个；
• 每层的入点之间，从小点向大点连边权为两者之差的边，从大点往小点连边权为 0 的边，只对 rank 相邻的点加边即可；
• 点 x 对应的 m 个入点均向出点连一条权值 c_x 的边；
• 每个出点向其对应的所有入点连一条边权为 0 的边，这是因为优化建图后可以直接走入点间的连边。

点数与边数均为 \Theta(nm) 级别。

建完图直接跑最短路即可。

完整赛时 AC 代码。