题解：P11598 [NOISG 2018 Finals] Safety
int4399
·
·
题解
$f_i(j)$ 显然是一个下凸函数，考虑证明。
- 当 $i=1$ 时，有 $f_1(x)=|x-a_1|$，这显然是下凸的。
- 当 $i>1$ 时，把转移看成两步，$f_i(j)=\min\limits_{k=\min(0,j-H)}^{j+H} f_{i-1}(k)$，这一步相当于左右取一个 $\min$，凸性保持不变。然后的转移是 $f'_i(j)=f_i(j)+|j-a_i|$，等价于给一个凸函数加上了一个凸函数，凸性仍然不变。得证。
考虑怎么维护。我们记最小值平台的范围是 $[L,R]$，如果一个点在 $[L-H,R+H]$ 范围内，那么它会变成最小值。否则会取到最靠中间的权值，这很符合直觉。我们记 最小值为 $base$，那么操作等价于令 $base\gets base+H$，即把左边的拐点左移，右边的拐点右移。
加上一个绝对值函数等价于在两边各插入一个 $a_i$，同时保留横坐标的单调性。这个的正确性比较好理解。因为相当于 $a$ 左右两边的线斜率都加 $1$，因此把这个拐点插进去即可。
总复杂度 $O(n\log n)$。
```
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
ll n,h,ans,base;
priority_queue<ll> l;
priority_queue<ll,vector<ll>,greater<ll>> r;
int main(){
cin>>n>>h;
for(ll i=1,a;i<=n;i++){
cin>>a,base+=h,l.push(a+base),r.push(a-base);
ll p=l.top()-base,q=r.top()+base;
if(p>q) l.pop(),r.pop(),ans+=p-q,l.push(q+base),r.push(p-base);
}return cout<<ans,0;
}
```