题解：D. Kousuke 的作业

问题重述

给定一个长度为 $n$ 的数组 $a$，我们需要找到最多不重叠的子段，使得每个子段的元素和为 $0$。

第一步：转化为前缀和问题

定义前缀和数组 $p$：

那么对于子段 $[l, r]$，其元素和为：

子段和为 $0$ 的条件等价于：

也就是说，一个子段是美丽的，当且仅当其左右端点对应的前缀和相等。

第二步：经典 DP 模型

这是一个典型的“最大不重叠区间”问题。

设 $dp[i]$ 表示考虑前 $i$ 个元素时，最多能选出的不重叠美丽子段数。

假设我们当前有一个美丽子段 $[l, r]$，那么：

其中：

• $dp[r-1]$ 表示不选当前子段；
• $dp[l-1] + 1$ 表示选当前子段，并加上前面的最优解。

我们按子段的右端点 $r$ 从小到大处理。
由于我们处理到 $r$ 时，所有 $i < r$ 的 $dp[i]$ 都已经计算完毕，因此该 DP 是可行的。

最终答案为 $dp[n]$。

第三步：针对本题的优化

如果对于某个右端点 $r$，存在多个 $l$ 使得 $p_{l-1} = p_r$，我们应该选哪一个？

我们只需要选 最大的 $l$（即最靠右的左端点）对应的子段。
为什么？

假设有两个左端点 $l_1 < l_2$ 都满足 $p_{l_1-1} = p_{l_2-1} = p_r$。
那么子段 $[l_2, r]$ 是 $[l_1, r]$ 的子段。
如果选了较长的 $[l_1, r]$，那么内部必然包含更短的 $[l_2, r]$，这会导致无法再选取内部的子段，从而可能错过最优解。
而选择最短的子段 $[l_2, r]$ 不会浪费内部可能存在的其他美丽子段。

因此，对于每个 $r$，若存在 $l$ 满足条件，我们只需要考虑最小的子段（即 $l$ 最大的那个）。

第四步：算法实现

1. 计算前缀和 $p_i$，$i = 0, 1, \dots, n$。
2. 使用哈希表（如 unordered_map）记录每个前缀和值最后一次出现的位置。
3. 遍历 $i = 1$ 到 $n$：
   • 若 $p_i$ 之前出现过，设其最后一次出现的位置为 $last$（注意：这里 $last$ 对应的是前缀和的下标，即子段的左端点为 $last+1$，右端点为 $i$）。
   • 对于这个子段 $[last+1, i]$，执行 DP：$$dp[i] = \max(dp[i-1],\; dp[last] + 1)$$
   • 否则：$$dp[i] = dp[i-1]$$
   • 更新 $p_i$ 的最新出现位置为 $i$。
4. 输出 $dp[n]$。

第五步：时间复杂度

• 每个前缀和值用哈希表存储，单次操作 $O(1)$。
• 遍历一次数组，总复杂度 $O(n)$。
• 排序或哈希表均可做到 $O(n)$ 或 $O(n \log n)$，这里实现为 $O(n)$。

示例验证

示例 1

数组：$[2, 1, -3, 2, 1]$
前缀和：$p = [0, 2, 3, 0, 2, 3]$

• $i=3$ 时，$p_3=0$ 上次出现在 $0$，子段 $[1,3]$ 和为 $0$，$dp[3] = \max(dp[2], dp[0]+1) = 1$
• $i=4$ 时，$p_4=2$ 上次出现在 $1$，子段 $[2,4]$ 和为 $0$，$dp[4] = \max(dp[3], dp[1]+1) = 1$
• $i=5$ 时，$p_5=3$ 上次出现在 $2$，子段 $[3,5]$ 和为 $0$，但 $dp[2]=1$，$dp[2]+1=2$，$dp[4]=1$，$dp[5] = 1$，因为最优是只选 $[1,3]$ 或 $[3,5]$ 中的一个。
  最终输出 $1$，与题意一致。

总结

本题的核心是：

• 转化为前缀和相等问题；
• 使用贪心选择最短子段；
• 用 DP 求最大不重叠区间数。

最终复杂度 $O(n)$。