# 菁英战斗兵题解

## 解法比较

出题人解法把正攻击的敌人按类型压缩成集合状态，以已清除类型为状态，保存能达到的最大生命值；非正攻击敌人的处理和每次连续清除一种敌人的归并，也来自出题人解法。状态相同时，更高生命值不会使后续选择变差，因此只保留最大值。一次清除的累计伤害是关于攻击次数的二次式，必须检查过程中的最大值，不能只看末值。

峰值位于二次式顶点附近的整数位置。Codex（GPT-6）的实现使用离散峰值判断和可移植大整数运算，精确处理峰值及超出 64 位的中间量，代价是大整数运算的常数开销。设正攻击类型数为 $k$ ，集合 DP 有 $O(2^k)$ 状态、$O(k2^k)$ 次转移；完整预处理与算术开销见下文。

## 整理战斗顺序

记每个单位需要的攻击次数为 $t_i=\lceil h_i/A\rceil$ ，实际数量为 $c_i$ . 忽略数量为零的兵种。

先固定铁狗的选择。每个剩余单位所需的攻击次数已经确定，因此消灭所有敌人所用的总回合数与攻击顺序无关。

考虑一次攻击非正攻击力单位的操作，以及它之后紧邻的一个完整正攻击力兵种处理过程。交换这两部分：将整个正攻击力兵种提前处理，再执行这一次攻击。这样正攻击力单位的死亡时刻只会提前；非正攻击力单位如果在这次攻击中死亡，死亡时刻只会推迟。因此在交换前后的每个对应回合，敌方攻击力总和都不会增大，鲍里斯的生命值都不会更低。交换也不破坏兵种锁定，因为移动的是一个完整兵种。反复交换后，所有非正攻击力单位都留到最后处理。

对同一个正攻击力兵种，集中火力逐个消灭即可。每个单位都需要 $t_i$ 次攻击，所以第 $j$ 次击杀最早发生在该兵种的第 $jt_i$ 次攻击，逐个击杀恰好能同时达到这些最早时刻。这样每回合存活的该兵种单位数都最少，只会减少净伤害。兵种锁定规则又要求整种连续处理，因此接下来只需决定正攻击力兵种之间的顺序。

铁狗移除一个非正攻击力兵种不会优于加血方案：保留它们到最后既不增加伤害，还可能回复生命。于是只需考虑加血，或移除一个实际存在的正攻击力兵种。

## 一个兵种的总伤害和途中峰值

当前处理的兵种记为数量 $c$ 、攻击力 $a>0$ 、每个单位所需攻击次数 $t$ . 其他存活敌人的攻击力之和为 $B$ ，包括所有回血单位的负攻击力。

已经消灭 $k$ 个该兵种单位时，累计净伤害为

$$D(k)=ktB+a\left(\frac{tk(2c-k+1)}2-k\right),\qquad 0\le k\le c$$

最后的 $-ak$ 来自被击杀者当回合不再反击。净伤害可以为负。

当 $t>1$ ，在已经消灭 $k$ 个单位、下一个只剩一击时，还应检查

$$Q(k)=D(k)+(t-1)\bigl(B+a(c-k)\bigr),\qquad 0\le k<c$$

两次击杀之间的非致命攻击不会改变敌人数量，这些回合的净伤害相同，所以最大累计伤害一定出现在某次击杀之后或紧邻击杀之前。最大值还需与初始值 $0$ 比较。

$D$ 和 $Q$ 都是凹二次序列，无需浮点求顶点：

$$D(k+1)-D(k)=t(B+ac)-a-ta\,k$$

$$Q(k+1)-Q(k)=t\bigl(B+a(c-1)\bigr)-ta\,k$$

对于首个差分为 $L$ 、差分每次减少 $s=ta>0$ 的序列，若 $L\le0$ ，取下标 $0$ ；否则取 $\lceil L/s\rceil$ ，再裁剪到合法下标范围。代回即可得到最大值。开始处理这一兵种时的生命值必须**严格大于**峰值，才能完成这一兵种。

不能只检查消灭整个兵种后的生命值。例如 $c=2,t=3,a=4,B=-5$ 时，各回合累计净伤害依次为 $3,6,5,4,3,-2$ . 初始生命值若为 $5$ ，虽然按总伤害计算会得到最终生命值 $7$ ，实际上第二回合就已经失败。

## 状态压缩动态规划

设 $S$ 是尚未消灭的正攻击力兵种集合，$f[S]$ 表示此时最大生命值。至多有 $20$ 种。

- 加血方案初始化 $f[\mathrm{All}]=H+\Delta H$ .
- 移除兵种 $i$ 的方案初始化 $f[\mathrm{All}\setminus\{i\}]=H$ .
- 不可达状态设为 $-1$ .

枚举状态和下一个处理的兵种。由 $S$ 可以确定其他存活敌人的攻击力之和 $B$ ，所有非正攻击力单位此时仍然存活。如果 $f[S]$ 严格大于上述峰值，用 $f[S]-D(c)$ 更新删除该兵种后的状态。相同剩余集合下，生命值较大的方案始终不劣，因此只保留最大值。按状态掩码从大到小转移即可，因为每次转移都会清除一个二进制位。若空集合仍不可达，输出 `leave!` .

## 最后处理回血和零攻击单位

先将每个单位打到只剩一次攻击即可消灭，期间不杀死任何单位。记所有这些单位每回合的总回复为 $R$ ，则此阶段回复

$$R\sum_i c_i(t_i-1)$$

然后按单个单位回复量 $-a_i$ 从小到大消灭。交换相邻两个击杀顺序可知，让回复量较大的单位多存活一回合更优。处理同种的 $c$ 个单位、每个回复量为 $r$ 时，若其他单位总回复为 $R'$ ，该阶段回复为

$$cR'+r\frac{c(c-1)}2$$

两步策略最优：如果一次非致命攻击排在某次击杀之后，将它前移到该击杀之前不会提前消灭任何单位，却能多保留一个回合的回复来源。因此可以先做完所有非致命攻击，再按上述顺序逐一击杀。这个阶段每回合生命值都不会下降，无需再检查生存条件；其总回复也与之前正攻击力兵种的处理顺序无关。

## 复杂度与数值安全

设实际存在的正攻击力兵种数为 $P$（Positive types），类型数为 $K$ ，单位数为 $N$ . 哈希查找名称在通常情况下读入耗时 $O(K+N)$（另计名称字节数），后续时间 $O(P2^P+K\log K)$ ，空间 $O(2^P+K)$（另计名称存储）。

不能只用有符号 64 位整数保存答案。例如 $50000$ 个生命 $10^5$ 、攻击力 $-10^5$ 的单位，在鲍里斯攻击力为 $1$ 时，光是保留所有单位的非致命攻击阶段就能回复 $24999750000000000000$ .

总回合数至多 $N\cdot10^5$ ，每回合攻击总和绝对值至多 $N\cdot10^5$ ，故全程数值量级不超过 $2.5\times10^{19}+2\times10^9$ . 标程用 `High * 1000000000 + Low` 表示精确有符号整数，其中 $0\le\mathrm{Low}<10^9$ . 加减法归一化；乘非负整数时先拆出乘数的高、低部分，使每个机器整数乘积都落在 64 位范围内。无需编译器专属整数类型或第三方库。峰值下标使用普通 64 位整数计算，整个算法不依赖浮点数。

代码中 `InitialHealth` 、`BorisAttack` 、`HealthBonus` 分别对应 $H,A,\Delta H$ ，`PositiveKinds` 对应 $P$ . $P$ 统计实际存在的正攻击力兵种；$K$ 统计输入声明的全部兵种。