题解：P6674 [CCO2019] Card Scoring

Mysterious_Cat · 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 的决策点。

代码自己写。