参考。
例题
P4597。
分析
很显然的，我们可以得到一个 \(O(n^2)\) 的 DP 做法。定义状态函数 \(f_{i,j}\) 表示前 \(i\) 个数，\(a_i=b_j\) 的最小操作次数。其中 \(b\) 为原序列排序去重的结果。那么有转移方程：\(f_{i,j}=\min\limits_{k=1}^{j} f_{i-1,k}+|b_j-a_i|\)。
不难发现，我们的 \(f(i,j)\) 是一个凸函数。因为对于 \(j\) 的增加，我们有 \(f_{i,j}\le f_{i,j-1}\)，证明略。而对于形如 \(g(x)=|x-a|\) 的函数，也是一个凸函数。对于一个凸函数 \(f(x),x \in \{a_i\}\)，我们用 \(a_i\) 来表示。具体的，当 \(f(a_i)\) 与 \(f(a_{i+1})\) 之间的斜率为 \(k\) 时，我们可以用 \(k+1\) 个 \(a_i\) 来表示在 \(a_i\) 到 \(a_{i+1}\) 的过程中，斜率增加量为 \(k\)。其中第 \(1\) 个 \(a_i\) 表示了这个点。这样，我们就直接把这个凸函数的形状表示出来了，只需要知道任意一个 \(f(x)\) 的值就能得到所有函数值。
那么对于这道题，斜率 \(k\) 的最大值为 \(0\)，因为我们取了前缀 \(\min\)。那么由于两个凸函数相加的结果为凸函数，则可以直接通过插入 \(a_i\) 的方式更新函数的表示。如果我们 \(a_i\) 这个点对应的更新之前的函数是在一个相邻斜率为 \(0\) 的区间内，则插入单点 \(a_i\) 就能表示。如果不是，那么在 \(a_i\) 之前的点斜率减少 \(1\)，之后的斜率增加 \(1\)，再与 \(0\) 取最小值。我们控制前面的斜率不变，则能够用 \(2\) 个 \(a_i\) 表示出斜率加 \(1\)。而加 \(1\) 之后的分界点（之后的点斜率大于 \(0\)）就是当前所有 \(a_i\) 中的最大值了。（貌似是的？）那么我们就只需要将最大值删除，再加入 \(2\) 个 \(a_i\) 来更新形状。
对于这道题，不难发现答案就是维护出的函数中，斜率为 \(0\) 时的纵坐标。那么对于斜率变化的情况，我们的纵坐标相当于是整体加上了最大值减去 \(a_i\)。斜率不变的情况不变。维护插入、删除、最大值可以直接使用优先队列。时间复杂度 \(O(n\log n)\)。
代码
for(re int i=1;i<=n;++i){
if(!qu.empty()&&qu.top()>a[i]) ans+=qu.top()-a[i],qu.pop(),qu.push(a[i]);
qu.push(a[i]);
}