P11239 [KTSC 2024 R2] 跳跃游戏 - Solution

strcmp · 2025-11-10 22:15:11 · 题解

感觉有点不明所以的题。

以下序列均为 1-index，假设 k | n，如果不是那么将序列末尾补 0 即可，显然不影响复杂度。

首先 \Theta(n) 的 dp 是显然的，考虑类似序列最大权独立集的转移就行。f_i 为只考虑前 i 个元素的得分，f_i \gets \max(f_{i - 1},\,f_{i - k} + a_i)，令 f_1 = a_1。

然后我们要在一个长度极长的序列上做这个东西，当然只能离散化，然后将极长相邻 a_i 相同的元素缩在一起，最后会得到一个长度 \Theta(q) 的序列，这是显然的（每次区间加，该序列长度至多加 2）。

直接对着原序列做，讨论非常复杂，考虑将原序列按下标模 k 分组，此时我们可以将原序列写为 \frac{n}{k} 个长度为 k 的序列，转移一个 f_{i} 的时候：

它可能来自上一层相同位置 +a_i，也可能取自前面已计算完的所有 f 的最大值。

• 已计算完毕的 f 单调不降，这是显然的，所以我们只用考虑上一层的 f。我们默认在线段树里面先将所有的 a_i 加好，这是若干个区间加，均摊 \Theta(q) 个。

• 我们的 f 要么来自上一层 +a_i，要么来自本序列的前面的某个 f。考虑这种差异的原因，当然是因为 a_i < a_{i - 1}（或者 f_{i - 1} 继承过来的更大），导致 i 往后的一段 a 跟 a_i 相同的元素 f 取 f_{i - 1} 更优秀。由于 f 具有单调性，这必然是 i 开头的一段区间，可以线段树上二分求出，然后做区间覆盖。

• 不难发现，对于 a_{i} 相同的相邻的 f，不可能后面的取 \max 前面却不取，所以只考虑 a_i 等价段开头的 f 即可。

• 还有一个问题，我们现在的复杂度是 \Theta(\frac{n}{k} + q \log q)，k 很小怎么办。

注意到有些层它们内部只有一个种类的 a，这时候我们就是线段树全局加若干个 a_i，来将一段非常长的相同的 a_i 快速做完。

时空复杂度 \Theta(q \log q)，可以通过。

这个做法常数比较大而且细节不少，代码等有时间写的时候放在评论区。