有的坦克进入攻城模式，有的还在砰砰砰砰砰砰！

消除浪费伤害的攻城攻击

以端点为目标的攻城攻击最多使生命值总和减少 $3$；当 $N=1$ 时，最多减少 $2$。坦克模式攻击能以不超过 $3$ 的费用产生相同的变化。因此，存在一个不对端点使用攻城模式的最优方案。

一次攻城模式攻击最多使生命值总和减少 $4$。如果因为生命值在 $0$ 处截断而浪费了任何伤害，实际减少的生命值总和就至多为 $3$。用坦克模式攻击产生完全相同的生命值变化，费用不超过 $3$，且能到达相同状态。因此，存在一个最优方案，使每次攻城攻击的伤害都被完整利用。

最大化攻城攻击次数

设对位置 $i$ 使用攻城模式的次数为 $x_i$。根据上述结论，去掉对端点的攻城攻击，令 $x_0=x_1=x_N=x_{N+1}=0$。每个位置都必须满足

$$x_{i-1}+2x_i+x_{i+1}\le a_i.$$

反过来，只要这些条件成立，就可以按任意顺序进行攻城攻击而不浪费伤害，再用坦克模式消除剩余生命值。设 $K=\sum_i x_i$，攻城攻击使生命值总和减少 $4K$，因此总费用为

$$3K+\sum_{i=1}^{N}a_i-4K=\sum_{i=1}^{N}a_i-K.$$

所以，只需最大化满足上述条件的非负整数 $x_i$ 的总和。

动态规划

令 $M=\max_i a_i$，$B=\lfloor M/2\rfloor$。每个 都在 到 之间。

在处理位置 $i$ 之前，定义 $\mathrm{dp}[p][q]$ 为：位置 $i-1$ 及之前的条件均满足，且 $x_{i-1}=p$、 时，已经确定的 的最大总和。不可行状态取负无穷。初始时 ，其余状态不可行。

选择 $r=x_{i+1}$ 后，当前位置的条件为 $p+2q+r\le a_i$，转移为

$$\mathrm{next}[q][r]=r+\max_{0\le p\le\min(B,a_i-2q-r)}\mathrm{dp}[p][q].$$

当 $i+1\ge N$ 时，只允许 $r=0$。对每个固定的 $q$，沿 $p$ 计算前缀最大值，即可在 $$ 时间内计算每次转移。处理完位置 后， 就是最多的攻城攻击次数。

转移枚举了所有可能的下一个次数，并且恰好检查当前位置的生命值条件。由归纳法可知，DP 保留了所有可行安排及其最大次数。答案为 $\sum_i a_i-\mathrm{dp}[0][0]$。

时间复杂度为 $O(N(B+1)^2)$，空间复杂度为 $O((B+1)^2)$。因为 ，所以 。使用 的写法也适用于所有生命值都为 的情况。

子任务

• 子任务 $1$：以当前生命值向量为状态，直接尝试两种攻击。时间为 $O(N\prod_i(a_i+1))$，空间为 。当 、 时，状态数至多为 。

Solution written by GPT6