题解：P11598 [NOISG 2018 Finals] Safety

zxh923 · 2025-10-27 10:56:18 · 题解

思路

首先我们写出朴素 dp：设 f_{i,j} 表示已经放好前 i 个位置，第 i 个位置的高度是 j 的最小代价。

那么转移就是：f_{i,j}\leftarrow\displaystyle\min_{k=j-H}^{j+H}f_{i-1,k}+|s_i-j|。然后不难发现，这个东西是下凸的。可以尝试使用 slope trick 做。

我们观察该 dp 的定义域与斜率的值域。发现定义域很大，但斜率的值域并不大，所以我们考虑维护拐点。

用 slope trick 做第一步应当先把式子拆成几部分，并观察这几部分在函数上的影响。

所以我们拆成 f_{i,j}\leftarrow \min f_{i-1,k} 和 f_{i,j}\leftarrow |j-s_i| 两步来看。

不难发现第一步就是，把最低段的左端点和右端点往两边扩展 H。

第二也是显然且套路的，相当于往函数上加一个 V 状物。那我们直接把 s_i 左边的部分斜率全部 -1，右边的部分斜率全部 +1 即可。

于是我们维护对顶堆。那么操作一就是直接对两个堆打标记，操作二就是在某个堆插入两个 s_i 并把这个堆的堆顶转移到另一个堆。

代码

#include<bits/stdc++.h>
#define int long long
#define N 1000005
#define mod 998244353
#define pii pair<int,int>
#define x first
#define y second
#define pct __builtin_popcount
#define mpi make_pair
#define inf 2e18
using namespace std;
int T=1,n,h,a[N];
void solve(int cs){
    if(!cs)return;
    cin>>n>>h;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    priority_queue<int>q1;
    priority_queue<int,vector<int>,greater<int>>q2;
    int t1=0,t2=0;
    q1.push(a[1]);
    q2.push(a[1]);
    int res=0;
    for(int i=2;i<=n;i++){
        t1-=h;
        t2+=h;
        if(a[i]>=q1.top()+t1&&a[i]<=q2.top()+t2){
            q1.push(a[i]-t1);
            q2.push(a[i]-t2);
        }
        else if(a[i]<q1.top()+t1){
            res+=q1.top()+t1-a[i];
            q1.push(a[i]-t1);
            q1.push(a[i]-t1);
            q2.push(q1.top()+t1-t2);
            q1.pop();
        }
        else{
            res+=a[i]-q2.top()-t2;
            q2.push(a[i]-t2);
            q2.push(a[i]-t2);
            q1.push(q2.top()+t2-t1);
            q2.pop();
        }
    }
    cout<<res<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // cin>>T;
    // init(3e5);
    for(int cs=1;cs<=T;cs++){
        solve(cs);
    }
    // cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
    return 0;
}