题解：P11598 [NOISG 2018 Finals] Safety

思路

首先我们写出朴素 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

并把这个堆的堆顶转移到另一个堆。

代码

CPP

#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;
}

题解：P11598 [NOISG 2018 Finals] Safety

文章操作

思路

代码

相关推荐

评论

题解：P11598 [NOISG 2018 Finals] Safety