史莱姆逃生 题解

思路

状态观察

无论左右移动如何交替，已经吸收的史莱姆总是构成一个包含起点 $k$ 的区间 $[l,r]$，当前生命值恰好是 $\sum_{i=l}^r a_i$。只要 $l=1$ 或 $r=n$，下一步即可走到出口。

做法

子任务 1：枚举移动顺序

当 $n\le10$ 时，从状态 $[l,r]$ 递归尝试吸收 $a_{l-1}$ 或 $a_{r+1}$。仅在新生命值非负时继续。递归树至多包含 $O(2^n)$ 个分支，空间复杂度 $O(n)$。

子任务 2：区间可达 DP

当 $n\le300$ 时，令 $f_{l,r}$ 表示区间 $[l,r]$ 能否被安全吸收。区间和由前缀和求出。初态为 $f_{k,k}=1$；按区间长度递增转移：若区间和非负，且 $f_{l+1,r}$ 或 $f_{l,r-1}$ 为真，则 $f_{l,r}=1$。出现 $l=1$ 或 $r=n$ 的可达状态即成功。

状态数和时间复杂度均为 $O(n^2)$，空间复杂度 $O(n^2)$。

子任务 3：双侧增益段

考虑起点左侧，按 $k-1,k-2,\ldots,1$ 的顺序扫描。维护当前段的总和 sum 与最小前缀和 mn：

• 穿过此段至少需要 $-\text{mn}$ 点已有生命值；
• 一旦 sum > 0，把它封成一个增益段。若能付出所需生命值，整段走完后生命值增加 sum，因此走完一定不劣；
• 扫到边界仍未得到正总和时，保留最后一段。只要能穿过它，就已经到达出口，不要求总和为正。

右侧同理。用两个指针分别指向左右两侧尚未处理的第一段。如果某段的需求不超过当前生命值，就吸收它并增加生命值；若该段到达边界则答案为 YES。若两侧当前段都无法吸收，则把任意一侧的负前缀吸收一部分只会降低生命值，不可能解锁另一段，所以答案为 NO。

每个元素只被扫描一次，时间复杂度 $O(n)$，空间复杂度 $O(n)$。所有和均须使用 64 位整数。

复杂度

指数搜索层的单组时间复杂度为 $O(2^n)$、递归空间为 $O(n)$；区间 DP 层的时间和空间复杂度均为 $O(n^2)$；满分算法对单组的时间和空间复杂度均为 $O(n)$。多组数据下把 $n$ 换成所有测试用例规模之和。

正确性证明

引理 1　一个增益段可被安全穿过，当且仅当进入该段前的生命值不少于该段最小前缀和绝对值。

证明　走过段内第 $j$ 个元素后的生命值为原生命值加该段前 $j$ 项之和；所有这些值非负恰等价于原生命值加最小前缀和非负。∎

引理 2　若当前生命值足以穿过某个正总和增益段，立即穿过它不会使任何未来可行方案失效。

证明　由引理 1，穿过过程安全；穿过后生命值增加正数，且只移除了同一侧已经越过的元素。因此所有尚未处理段的需求不变，而可用生命值不减。∎

引理 3　若左右两侧当前段都无法穿过，则不存在逃生方案。

证明　抵达任一出口前，必须先从某一侧当前段的开头继续。完整穿过该段不安全；而只吸收其尚未完成的负前缀会使生命值更小，不能让另一侧从不可穿过变为可穿过。故不存在安全的第一步序列。∎

定理　算法输出 YES 当且仅当存在合法逃生方案。

证明　算法输出 YES 时，每个已穿过段均由引理 1 保证安全，最后一段抵达边界，故方案合法。反之，算法不断由引理 2 安全地吸收可用增益段；若抵达边界则成功，否则只会停在两侧均不可穿过的状态，由引理 3 此时确实无解。∎