Armor and Weapons 题解

思路

已经拥有的护甲中，编号更大的护甲不会比编号更小的差；武器同理。因此任意时刻只需记录当前最大的护甲编号 $a$ 与最大的武器编号 $b$。

若 $(a,b)$ 是协同组合，当前能达到的最大战斗力为 $a+b+1$；否则为 $a+b$。任何不是 $(a,b)$ 的旧组合都不可能给出更大的战斗力：只要至少一个编号比当前最大编号小，它即使得到额外的 $1$，也至多追平 $a+b$。

于是从状态 $(a,b)$ 花一小时只有两种有意义的转移：

$$(a,b)\to(\min(n,p),b),\qquad (a,b)\to(a,\min(m,p)),$$

其中 $p=a+b+[(a,b)\text{ 是协同组合}]$。

子任务一：枚举操作序列

当 $n,m\le12$ 时，逐渐增加允许的操作次数，并递归枚举每一步升级护甲或升级武器。第一次能够到达 $(n,m)$ 的深度就是答案。这是直接从题意出发的指数算法。

子任务二：完整状态图 BFS

当 $n,m\le1000$ 时，把所有 $(a,b)$ 看成图上的顶点，上述两种升级看成单位边。从 $(1,1)$ 做 BFS，即可在 $O(nm)$ 个状态内求最短路。

子任务三：逐层维护 Pareto 前沿

完整范围无法保存 $nm$ 个状态。考虑 BFS 的同一层：如果状态 $(a_1,b_1)$ 满足 $a_1\ge a_2$ 且 $b_1\ge b_2$，那么 $(a_2,b_2)$ 可以被删去。前者已经拥有不差的两类装备，之后能模拟后者的每一步。

因此每层生成所有后继后，按护甲编号从大到小排序，只保留武器编号严格超过此前最大值的状态。保留下来的状态两两不可支配，构成 Pareto 前沿。

协同点只会让某个精确状态多增长 $1$。算法只显式维护每层的不可支配状态，配合平衡树查询协同组合即可通过完整范围；在一维很小时层数可以达到线性，因此数据中也必须覆盖这种退化形态。

做法

1. 把全部协同组合存入集合。
2. 初始前沿只有 $(1,1)$，答案为 $0$。
3. 对当前前沿中的每个状态计算最大战斗力，并生成升级护甲、升级武器两个后继。
4. 将后继按第一维降序、第二维降序排序。
5. 扫描排序后的后继，只保留第二维严格大于已保留最大值的状态。
6. BFS 层数加一；当前沿变为 $(n,m)$ 时输出层数。

正确性证明：

• 由编号单调性，任意策略都可以只使用当前最大护甲和最大武器；旧组合不会产生比 $(a,b)$ 更高的可购买编号。因此两条转移包含了全部最优选择。
• BFS 每层恰好表示花费相同小时数能到达的状态，所以第一次到达 $(n,m)$ 时层数最小。
• 若一个同层状态被另一个状态逐维支配，支配状态已经拥有被支配状态的所有有效购买能力，能够模拟其后续策略。删除被支配状态不会删除任何最优解。
• 归纳每一层，维护的前沿与完整 BFS 在可到达终点的最短层数上等价，故算法输出最少小时数。

复杂度

设所有层中处理的前沿状态总数为 $S$。

• 子任务一的时间复杂度为 $O(2^d)$，其中 $d$ 是答案；递归空间为 $O(d)$。
• 子任务二的时间复杂度和空间复杂度均为 $O(nm)$。
• 完整算法的时间复杂度为 $O(S\log S+S\log q)$，空间复杂度为 $O(q+S)$，其中 $S$ 是所有 BFS 层实际处理的前沿状态总数；一维封顶后的线性增长也计入 $S$。