官方题解（中文整理）

基于 Eva Zhu 的官方题解整理。

先从朴素 DP 观察状态

最暴力的做法是枚举所有子集，复杂度 \(O(2^N \cdot N)\)，显然无法接受。

进一步考虑 DP。若按位置从左到右扫描，一个营员是否能被选，只取决于它左边最近的、仍在有效距离内的被选教练。

因此，一个自然的状态是记录“当前最右边被选中的教练是谁”。

\(O(N^2)\) 的状态设计

设 \(dp_{i,j}\) 表示处理完前 \(i\) 头奶牛后，最右边被选中的教练恰好是 \(j\) 的好子集数量。

分类讨论：

• 如果第 \(i\) 头奶牛是教练，那么它既可以不选，也可以作为新的最右教练被选
• 如果第 \(i\) 头奶牛是营员，那么只有当最右教练 \(j\) 与它的距离不超过 \(D\) 时，它才能被选；否则它只能不选

这样可以得到一个 \(O(N^2)\) 的 DP。

正解思路：只关心“仍然活跃的教练”

对于一个营员 \(i\)，它能否被选中，只和左侧那些满足：

\(p_i - D \le p_j < p_i\)

的教练有关。更准确地说，只和这些教练中“最右边被选中的那个”有关。

于是我们定义：

\(f_j\)

表示当前已处理前缀内，最右边被选中的教练正好是 \(j\) 的好子集数量。

当处理一个营员时：

• 如果某个教练状态 \(j\) 仍在有效窗口中，那么这个营员可以“选”或“不选”，对应 \(f_j\) 乘以 \(2\)
• 若 \(j\) 已经不在窗口中，那么该营员不能被选，\(f_j\) 不变

当处理一个教练时：

• 可以把它接到当前任意一个好子集后面，作为新的最右教练

用滑动窗口优化到 \(O(N)\)

如果每遇到一个营员都把所有活跃教练的 \(f_j\) 乘以 \(2\)，仍会超时。为此使用懒标记思想。

维护：

• 一个队列，存当前仍然活跃的教练
• 一个乘法因子 \(mul\)，表示“所有活跃教练状态共同被乘了多少次 \(2\)”
• 令 \(f_j = g_j \cdot mul\)，只显式维护 \(g_j\)

同时维护：

• \(fsum\)：已经滑出窗口、不再活跃的教练状态总和
• \(gsum\)：仍在窗口中的 \(g_j\) 之和

那么当前所有非空好子集总数就是：

\(fsum + gsum \cdot mul\)

再加上空集，就得到把新教练加入时可承接的总方案数。

处理营员

若当前奶牛是营员，那么所有仍活跃的教练状态都翻倍。无需逐个修改，只需令：

\(mul \gets 2 \cdot mul\)

处理教练

若当前奶牛是教练，那么它作为“新的最右教练”的状态数量，就是当前所有好子集数量（包括空集）：

\(1 + fsum + gsum \cdot mul\)

为了与现有表示法一致，把这个值除以当前 \(mul\) 后存成新的 \(g_j\) 即可。

维护滑出窗口的教练

当队首教练的位置已经小于 \(p_i-D\) 时，它不再能服务于后续营员，应从活跃集合中移出，并把对应的 \(f_j\) 加入 \(fsum\)。

整个过程中，每头奶牛至多入队、出队一次，因此总复杂度线性。

复杂度

总时间复杂度 \(O(N)\)，空间复杂度 \(O(N)\)。