菁英战斗兵题解¶

解法比较¶

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

峰值位于二次式顶点附近的整数位置。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\) 统计输入声明的全部兵种。