# 战斗属性的升级计划：题解 **出题人解法：整除值变化事件与单调防御指针。GPT-6 补充凸性、平局和整数安全证明，提供标准 C++17 实现及堆调度补充方案。** ## 1. 固定攻击和防御 设攻击、防御的升级次数为 $x,y$ ，于是 $$ A=A_0+xV_A,\qquad D=D_0+yV_D. $$ 必须有 $A>d_i$ .击败一名第 $i$ 种敌人要 $$ t_i(x)=\left\lceil\frac{h_i}{A-d_i}\right\rceil $$ 回合。因为同时攻击，最后一回合敌人也会造成伤害。全部敌人的总伤害为 $$ F_x(y)=\sum_i k_it_i(x)\max(a_i-D_0-yV_D,0). $$ 伤害均非负，不回血，因此战斗顺序不影响生存条件。最小升级后生命为 $$ H=\max(H_0,F_x(y)+1), $$ 花费为 $xC_A+yC_D+(H-H_0)C_H$ . 攻击升级次数只需考虑 $$ L=\max\left(0,\max_i\left\lceil\frac{d_i+1-A_0}{V_A}\right\rceil\right), \quad R=\max\left(0,\max_i\left\lceil\frac{d_i+h_i-A_0}{V_A}\right\rceil\right). $$ 低于 $L$ 无法击败某些敌人，高于 $R$ 不再减少回合数。防御次数不超过 $$ Y=\max\left(0,\max_i\left\lceil\frac{a_i-D_0}{V_D}\right\rceil\right). $$ 达到 $Y$ 时完全不受伤。即使某类敌人不能造成伤害，也要用它的防御更新攻击下界。 ## 2. 防御的凸性与单调性 固定 $x$ ，$F_x(y)$ 是若干非负折线的和，关于整数 $y$ 离散凸且不增。加血量 $\max(F_x(y)+1-H_0,0)$ 仍然凸，加入线性的防御价格后，总费用关于 $y$ 也凸。 从最大防御 $Y$ 开始，只在减少一次防御能**严格**减少费用时左移，停在费用最小的最大防御次数。若相邻防御费用相同，较高防御对应更小的生命：防御单价为正，相同总费用必须由更多加血补偿较低防御。因此保留较高防御符合先比较生命的字典序。 攻击提高后，每种敌人的回合数都不增。对于固定相邻防御 $y-1,y$ ，它们的总伤害差不增，较低防御下的总伤害也不增。加血差等于这两个非负量中的较小者： $$ \min\left(F_x(y-1)-F_x(y),\ \max(F_x(y-1)+1-H_0,0)\right). $$ 所以增加防御的节省额随攻击提高而不增，最大最优防御次数不会向右移动。整个攻击扫描只需一个总共左移 $Y$ 次的指针。 ## 3. 只在回合数改变时更新 $\lceil h/d\rceil=\lfloor(h-1)/d\rfloor+1$ 只有 $O(\sqrt h)$ 个不同值。若当前回合数为 $t>1$ ，下一次降低回合数所需的最小伤害为 $$ d'=\left\lceil\frac{h}{t-1}\right\rceil. $$ 将 $d'$ 换算成最小攻击升级次数，即 $$ x'=\left\lceil\frac{d_i+d'-A_0}{V_A}\right\rceil. $$ 它严格大于当前次数，可能一次跳过多个回合数。重复该过程即可列出每种敌人的全部变化事件。 出题人解法将事件挂到以攻击次数为下标的链表中，顺序扫描。没有事件时，伤害函数不变而攻击费用增加，故只在 $L$ 和事件位置评价答案。参考程序动态按 $R$ 分配下标数组，事件数记为 $E=O(\sum_i\sqrt{h_i})$ . ## 4. 防御桶 对于会造成伤害的敌人，写 $$ a_i-D_0=p_iV_D+r_i,\qquad 0\le r_i