自动搬运

查看原文

来自洛谷，原作者为

	Mysterious_Cat 无欲无求

搬运于2025-08-24 22:22:59，当前版本为作者最后更新于2024-09-11 20:49:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

记 $f_i$ 为前 $i$ 个数，以 $i$ 为最后一段结尾的最大得分。不难发现我们一定使用颜色 $c_i$ 作为最后一段的颜色。否则我们可以在 $i - 1$ 结束。同理，最后一段开头颜色也是 $c_i$。由此可知我们的决策点 $j$ 必然满足 $c_j = c_i$。

由此得知转移方程：$f_i = \max\limits_{j \le i \wedge c_j = c_i} \{f_{j - 1} + {cnt_{j,i,c_i}}^k, {cnt_{1,i,c_i}}^k \}$。其中 $cnt_{l,r,c}$ 表示区间 $[l,r]$ 中 $c$ 的出现次数。

对于任意 $j_1 < j_2 \le i$ 满足 $j_1, j_2$ 都是 $i$ 的决策点，都有 ${cnt_{j_1,i,c_i}}^k$ 比 ${cnt_{j_2,i,c_i}}^k$ 的增长速度快。如果某一时刻 $f_{j_1 - 1} + {cnt_{j_1,i,c_i}}^k \ge f_{j_2 - 1} + {cnt_{j_2,i,c_i}}^k$，$j_1$ 将一直优于 $j_2$。于是我们对每种颜色维护 $f_{j - 1} + {cnt_{j,i,c_i}}$ 递增的栈，同时二分求出栈中相邻两元素大小顺序改变的时间，当 $i$ 大于这个时间就把靠后的元素扔掉。

但是这样我们需要扔掉栈中间的元素，还要维护最小交换时间，可以用 set 做到 $O(n \log n)$，但是常数太大了，过不去。我们再分析一些性质。

如果三项元素 $j_1 < j_2 < j_3$ 满足 $j_1, j_2$ 交换先于 $j_2, j_3$，那么 $j_2$ 必然不可能成为最优决策点。于是我们在原单调栈基础上加一个交换时间递减的限制。这样我们进来一个元素只需要不断弹掉栈顶直到符合限制。每次查询栈顶即为最优决策点。

注意这里 $i$ 是 $i$ 自己的决策点。要先将 $i$ 入栈再查询 $i$ 的决策点。

代码自己写。