题解

思路

若选择第 $p$ 个怪物作为爆炸中心，普通攻击后仍由连锁爆炸击杀的怪物必须构成包含 $p$ 的连续段。它们的生命值从 $p$ 向两侧每走一步至少下降 $1$。为了节省最多普通攻击，应在不超过初始生命值的前提下尽量保留这些生命值。

设 $L_i$ 为以 $i$ 作为最右端、向左每步至少减一时能保留的最大生命值总和，$R_i$ 对称定义。若原数组总生命值为 $S$，以 $i$ 为中心的总代价为

其中 $h_i$ 在 $L_i,R_i$ 中各计算一次，而最后还要支付 $h_i$ 点爆炸能量。

做法

平方做法枚举中心后向两侧贪心令当前生命值为 min(初始生命值, 上一个生命值-1)。

满分做法线性求 $L$。处理位置 $i$ 时，需要找到最近的 $j<i$，满足 $h_j-j\le h_i-i$；同时保留生命值不能降到零，所以还有边界 $j\ge i-h_i$。最近合法位置由维护 $h_j-j$ 的单调栈得到。设 $len=i-j$，则新形成的等差段贡献

若没有在零处截断，再加上 $L_j$。反转数组同样计算 $R$，最后枚举中心取最小值。

复杂度

每个位置至多进栈、出栈一次，时间复杂度为 $O(\sum n)$，空间复杂度为 $O(\max n)$。