P11598题解

· · 题解

1 思路

我们不必限制柱子的高度必须是整数，也不必限制必须是非负数。因为调整法可以证明如果柱子的高度不是非负整数就一定不优。

首先考虑动态规划。设 dp_{i,j} 为：只考虑前 i 柱并且第 i 柱高度必须是 j 时的最小代价。

边界情况是 dp_{0,j}=0。可以容易地写出转移：

dp_{i,j}=\min_{k=j-H}^{j+H}dp_{i-1,k}+|j-S_i|

答案则为 dp_N 的最小值。

直接计算这个式子显然是无法通过的。但是我们发现 dp_i 一定是个下凸函数：因为 dp_{0,j}=0，而之后的操作也不会破坏下凸的性质。

再分析这个式子。可以化为对 dp_i 的如下两个修改操作：

dp_{i,j}\gets\min_{k=j-H}^{j+H}dp_{i-1,k} dp_{i,j}\gets|j-S_i|

第一个操作实际上是将常函数段左侧往左平移 H，常函数段右侧往右平移 H，类似“拉扯”。第二个操作实际上是加上一个简单的 V 形函数。

可以考虑用两个优先队列分别维护常函数段左侧和常函数段右侧的折点，同时维护常函数段的值。

第一个操作只需要打个标记。第二个操作要分讨 V 形函数的顶点在常函数段横坐标范围里还是两侧，并修改常函数段横坐标范围；如果是两侧还需还需要计算常函数段的值的变化。

时间复杂度 \Theta(N\log N)。

2 代码与记录

#include<bits/stdc++.h>
using namespace std;
#define max_n 200000
#define inf ((long long)2e9)
int n;
long long lim;
long long a[max_n+2];
priority_queue<long long>ql;
priority_queue<long long,vector<long long>,greater<long long>>qr;
long long low=0;
long long tagl=0,tagr=0;
int main(){
    #ifdef dzy
    freopen("P11598_1.in","r",stdin);
    freopen("P11598_1.out","w",stdout);
    #endif
    scanf("%d%lld",&n,&lim);
    for(int i=1;i<=n;++i)scanf("%lld",a+i);
    ql.push(-1); qr.push(inf); low=0;
    for(int i=1;i<=n;++i){
        tagl-=lim; tagr+=lim;
        long long l=ql.top()+tagl,r=qr.top()+tagr;
//      printf("l=%lld r=%lld low=%lld\n",l,r,low);
        if(l<=a[i]&&a[i]<=r){ql.push(a[i]-tagl); qr.push(a[i]-tagr);}
        else if(a[i]<l){
            low+=l-a[i];
            ql.push(a[i]-tagl); ql.push(a[i]-tagl);
            qr.push(ql.top()+tagl-tagr); ql.pop();
        }
        else{
            low+=a[i]-r;
            qr.push(a[i]-tagr); qr.push(a[i]-tagr);
            ql.push(qr.top()+tagr-tagl); qr.pop();
        }
    }
    printf("%lld\n",low);
    return 0;
}

记录传送门

By dengziyue