题解 P4597 【序列sequence】
Mr_Wu
·
·
题解
前言
smarthehe 神看我最近总不刷题就给我推了 CF713C，然后我猜了 dp 是下凸壳，然后给猜对了。。然后找到了三倍经验：CF713C、CF13C、还有这题。。
然后我也采用了大部分题解使用的写法，我认为出处应该来自于 ko_osaga，我将会做详细解释。
题解
首先我们弄出一个 dp，设 f_{i,j} 表示到第 i 个数，把这个数变成 j，考虑 [1,i] 的最小代价，转移方程是
f_{i,j}=\min_{k\le j} f_{i-1,k} +|a_i-j|
所以现在我们有了一个 \Theta(n\max a_i) 的复杂度，实在是太好了，能通过 0 个加强前题目的数据！
接下来我们来证明对每个 i，f_{i,x} 是关于 x 的一个下凸壳。
首先 i=1 的时候是的对吧。。
然后我们考虑每次发生了什么变化，
（线段上标的是斜率，图中画的线段斜率可能不太准）
分 4 种情况，讨论下凸壳中的每一个线段：
- 线段单降，在 a_i 左侧
此时 \min\limits_{k\le j} f_{i-1,k}=f_{i-1,j}，所以 f_{i,j}=f_{i-1,j}+a_i-j，稍微看看就能发现是斜率减 1 。（数值 -1，不是绝对值 -1 ！）
- 线段单降，在 a_i 右侧
仿效上面的方法，f_{i,j}=f_{i-1,j}+j-a_i，是斜率增 1 。
- 线段不单降，在 a_i 左侧
此时找到之前最后一个单降的点 \text{op}，则 f_{i,j}=\text{op}+a_i-j，此时线段斜率变成 -1 。
- 线段不单降，在 a_i 右侧
因此这是个凸包，直接按照上面的方法，可以有 $\Theta(n^2)$ 了。
然后我们考虑用数据结构维护凸包，其实我们有一个很简单的方法，就是直接使用大根堆，堆中每个元素应当是二元组 $(x,k)$ 表示一条线段的右端点和这条线段的斜率，并且我们舍弃掉所有不单降的线段，**但是考虑到 priority_queue 可重，我们舍弃掉第二个元素，然后我们认为一个元素的 $k$ 是与它相同的最左边的元素到最大元素之间的距离的相反数**。例如用 $\{1,2,3,3\}$ 表示 $\{(1,-4),(2,-3),(3,-2),(3,-2)\}$。
我们加入了 $a_i$，两种情况：
1. $a_i\ge \text{op}$，此时 $a_i$ 成为新的决策点，我们不需要更新答案，只需要压如 $a_i$。
2. $a_i<\text{op}$，此时所有堆中的斜率都 -1，斜率为 -1 的应当弹出，由于这个写法很聪明，因此只需要把最大的元素弹出，在弹出之前更新答案。
### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, t; long long ans;
priority_queue<int> Q;
int main() {
scanf("%d", &n);
while (n--) {
scanf("%d", &t), Q.push(t);
if (Q.top() != t) ans += Q.top() - t, Q.pop(), Q.push(t);
} printf("%lld\n", ans);
return 0;
}
```