P4597 序列 sequence

经典的凸包优化，运用到 slope trick。感觉还是挺妙的。

考虑朴素 DP。设 $f(i,j)$ 表示第 $i$ 个数变为 $j$ 的最小花费，状态转移方程为：

$$f(i,j)=\underset{k\le j}{min}f(i-1,k)+|a_i-j|$$

相当于先进行一次前缀 $min$，再加上绝对值。将 $f(i,j)$ 视作关于 $j$ 的函数，容易发现这是一个凸函数。因为初始函数 $f(1,j)$ 是凸函数 ，而我们每次进行前缀取 $min$ 以及加上一个凸函数，都能够保证得到的新函数保持凸性，并且其中线段斜率为整数。

如何维护这个凸包？我们考虑维护每一个转折点，考虑一个序列，序列中每个转折点 $x$ 表示再在位置 $x$ 斜率增加 $1$。那么我们加入一个绝对值函数 $|a_i-x|$，相当于插入两个转折点 $a_i,a_i$。由于前缀取 $min$ 的存在，我们只需要保留斜率大于 $0$ 的部分即可。而对于当前最优解就是最右边的端点。这用堆很容易维护，于是我们对于 $a_i$ 进行如下操作：

1. 在堆中加入两个转折点 $a_i,a_i$。
2. 取出此时最右边的端点，设为 $x$。因为前面加入了两个端点，$y<x$ 的转折点斜率全部减 $1$，$x$ 之后的直线斜率变为 $1$。此时 $x$ 即为最优。所以答案直接加上 $x-a_i$。
3. 因为 $x$ 之后的直线斜率变为 $1$，我们直接将 $x$ 扔掉即可。

重复以上过程即可，时间复杂度 $\mathcal{O}(n\log n)$。

Code

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n;
long long ans;
priority_queue<int>q;
int main()
{
    read(n);
    while(n--)
    {
        int x;
        read(x);
        q.push(x);
        if(x<q.top())ans+=q.top()-x,q.pop(),q.push(x);
    }
    printf("%lld\n",ans);
    return 0;
}