CF1787H Codeforces Scoreboard 题解

· · 题解

可能更好的阅读体验
upd: 2023.11.9 突然想到想来修缮一下题解。
什么时候给的黑，感觉应该不至于?
DP 优化部分感谢 @rsjw 的 slope trick 思路。

solution

首先不考虑对 a_i 取 \max，显然直接按照 k 降序排序最优。
接下来考虑 a_i 的限制，如果取到了 a_i 一定放在最后面最优。
为了方便设 f_{i,j} 为前 i 个，j 个数字不取 \max，最后答案和 \sum b 的差的最小值。
设 lim_i=b_i-a_i

f_{i,j}=\left\{ \begin{aligned} f_{i-1,j}+lim_i & & j=0 \\ \min\{f_{i-1,j}+lim_i,f_{i-1,j-1}+k_i\times j\} & & j>0 \end{aligned} \right.

这样时间复杂度为 \Theta\left(n^2\right)。

考虑优化。
首先对于样例输出一个整个 f。
我们通过观察样例发现对于给定的 i，在 j 改变的时候是下凸的。 对 j 一维差分，设 g_{i,j}=f_{i,j}-f_{i,j-1}(j>0)。
我们可以发现 g_i 到 g_{i+1} 的变化似乎很有规律，可以试着直接用数据结构来优化这个转移（slope trick）。
我们利用 f_{i,j} 的转移把 g_{i,j} 的转移算出来 默认 1<j<i，将 f_{i,j}=f_{i,0}+\sum\limits_{k=1}^jg_{i,k} 带入 f_{i,j} 的递推式。

得到

f_{i,0}+\sum_{k=1}^{j}g_{i,k}=\min\{f_{i-1,0},\sum_{k=1}^{j}g_{i-1,k}+lim_i,f_{i-1,0}+\sum_{k=1}^{j-1}g_{i-1,k}+k_i\times j\}

化简得

lim_i+\sum_{k=1}^{j}g_{i,k}=\sum_{k=1}^{j-1}g_{i-1,k}+\min\{g_{i-1,j}+lim_i,k_i\times j\}

对于上式用 j-1 代替 j

lim_i+\sum_{k=1}^{j-1}g_{i,k}=\sum_{k=1}^{j-2}g_{i-1,k}+\min\{g_{i-1,j-1}+lim_i,k_i\times (j-1)\}

两式相减，得到

g_{i,j}=g_{i-1,j-1}+\min\{g_{i-1,j}+lim_i,k_i\times j\}-\min\{g_{i-1,j-1}+lim_i,k_i\times (j-1)\}

由于 k 单调不增，对 i 归纳可以发现，对自变量 j，g_{i-1,j} 的增长速度不会比 k_i\times j 慢。所以随着 j 的增大，存在一个分界点，使得 \min\{g_{i-1,j}+lim_i,k_i\times j\} 前一段的取到 g_{i-1,j}，后一段取到 lim_i,k_i\times j。

因此，从 g_i 到 g_{i+1}，分别是三段转移：第一段不变，第二段为新增加的一个数字，第三段区间加一个数。

最后答案为最大前缀和。

用平衡树维护这个变化过程，O(n\log n)。

https://codeforces.com/contest/1787/submission/191206679