【题解】「CEOI2017」Building Bridges 斜率优化 DP loj#2483/luoguP4655 —Qiuly

愉快的推式子吧 (ﾉ≧∀≦)ﾉ！

设 $f_i$ 表示前 $i$ 根柱子完工后的最小代价。枚举一个小于 $i$ 的 $j$ ，表示为从 $j$ 向 $i$ 连了一座桥，中间的柱子当然全部推掉，计算一下就好：

$f_i=\min{f_j+(s_{i-1}-s_j)+(h_i-h_j)^2}$

*其中 $s$ 为 $w$ 的前缀和。

$f_i=f_j+(s_{i-1}-s_j)+(h_i-h_j)^2\\f_i=f_j+s_{i-1}-s_j+h_i^2+h_j^2-2h_ih_j\\f_j+s_{i-1}-s_j+h_i^2+h_j^2=2h_ih_j+f_i$

于是最终式子变成了 $y=kx+b$ 的形式，斜率优化！

但是…… 注意这个式子的 $k$ 不是单调递增的，并且 $x$ 也不是单调递增的！那么我们不能用朴素做法了，也不能用二分…… 难道用 $Splay$ ？(码量巨大) 。

不，用 $CDQ$ 分治。

对于一个 $i$ ，可能可以对 $i$ 做出贡献的只有所有小于 $i$ 的 $j$ 。为了保证 $x$ 单调我们先大力将原来的数组按照 $x$ 从小到大排个序，然后 $CDQ$ 的时候分左右两边，左边的所有元素在初始数组的位置都小于右边的左右元素，也就是说我们直接用左边元素对右边元素做出贡献。

同时这里也保证了左右两边的 $x$ 一定是单调上增的。

我们使用单调队列，扫一遍左边的元素，留下能做贡献的点 (下凸壳上的点)，这时候左边的所有元素可以保证 $x$ 和斜率都是单调上增的。

右边呢？因为直线的斜率是 $2x$ ，而右边的 $x$ 也是单调上增的，所以我们可以愉快的做朴素的单调队列了。

$CDQ$ 分治部分的代码：

void CDQ(int l,int r) { 
    if(l==r) {/*一个点的时候直接计算 y 值*/
        a[l].y=f[a[l].id]-s[a[l].id]+S(a[l].x);
        return;
    }
    int mid=(l+r)>>1;
    for(int i=l,c1=l,c2=mid+1;i<=r;++i) 
        if(a[i].id<=mid) b[c1++]=a[i]; /*编号小的左边去*/
        else b[c2++]=a[i]; /*编号大些的右边去*/
    for(int i=l;i<=r;++i) a[i]=b[i];
    CDQ(l,mid); /*计算出左边所有元素的 f*/
    int head=1,tail=0;
    static int q[N];
    for(int i=l;i<=mid;++i) { /*处理出左边所有元素组成的下凸壳*/
        while(head<tail&&slope(q[tail-1],q[tail])>slope(q[tail],i)) --tail;
        q[++tail]=i;
    }
    for(int i=mid+1;i<=r;++i) { /*计算左边元素对右边元素产生的贡献*/
        while(head<tail&&slope(q[head],q[head+1])<2*a[i].x) ++head; /*维护队列*/
        int x=a[i].id,y=a[q[head]].id;
        f[x]=min(f[x],f[y]+s[x-1]-s[y]+S(a[i].x-a[q[head]].x));
        /*可能计算多次所以要取 min*/
    }
    CDQ(mid+1,r);
    for(int i=l,c1=l,c2=mid+1;i<=r;++i)  /*还原 a 数组至初始状态*/
        if(c2>r||(c1<=mid&&a[c1].x<a[c2].x)) b[i]=a[c1++];
        else b[i]=a[c2++];
    for(int i=l;i<=r;++i) a[i]=b[i];
    return;
}

//main 函数中
sort(a+1,a+1+n,cmp),CDQ(1,n); /*排序后 CDQ 开始*/
printf("%lld\n",f[n]); /*输出*/

最后因为存在 $0$ ，在计算斜率的时候需要特判一下。还需要注意一下 $long\ long$ 的问题，记得将 $f$ 数组初始化。

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e5+2;
const ll inf=1e18+9;

struct point {int x,id;ll y;}a[N],b[N];
ll s[N],w[N],f[N];int n;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

ll S(ll x) {return x*x;}
bool cmp(point x,point y) {return x.x<y.x;}
double slope(int i,int j) {
    if(a[i].x==a[j].x) {
        return a[i].y<a[j].y?inf:-inf;
    }return double(a[i].y-a[j].y)/double(a[i].x-a[j].x);
}

void CDQ(int l,int r) {
    if(l==r) {a[l].y=f[a[l].id]-s[a[l].id]+S(a[l].x);return;}
    int mid=(l+r)>>1;
    for(int i=l,c1=l,c2=mid+1;i<=r;++i) 
        if(a[i].id<=mid) b[c1++]=a[i];
        else b[c2++]=a[i];
    for(int i=l;i<=r;++i) a[i]=b[i];
    CDQ(l,mid);
    int head=1,tail=0;
    static int q[N];
    for(int i=l;i<=mid;++i) {
        while(head<tail&&slope(q[tail-1],q[tail])>slope(q[tail],i)) --tail;
        q[++tail]=i;
    }
    for(int i=mid+1;i<=r;++i) {
        while(head<tail&&slope(q[head],q[head+1])<2*a[i].x) ++head;
        int x=a[i].id,y=a[q[head]].id;
        f[x]=min(f[x],f[y]+s[x-1]-s[y]+S(a[i].x-a[q[head]].x));
    }
    CDQ(mid+1,r);
    for(int i=l,c1=l,c2=mid+1;i<=r;++i) 
        if(c2>r||(c1<=mid&&a[c1].x<a[c2].x)) b[i]=a[c1++];
        else b[i]=a[c2++];
    for(int i=l;i<=r;++i) a[i]=b[i];
    return;
}

int main() {
    IN(n);
    for(int i=1;i<=n;++i) 
        IN(a[i].x),a[i].id=i,f[i]=inf;
    f[1]=0;
    for(int i=1;i<=n;++i) IN(w[i]),s[i]=s[i-1]+w[i];
    sort(a+1,a+1+n,cmp),CDQ(1,n);
    printf("%lld\n",f[n]);
    return 0;
}

【题解】「CEOI2017」Building Bridges 斜率优化 DP loj#2483/luoguP4655 —Qiuly

于2019年4月27日由Qiuly发布

Code:

Qiuly

0 条评论

发表回复取消回复

【题解】「CEOI2017」Building Bridges 斜率优化 DP loj#2483/luoguP4655 —Qiuly

于2019年4月27日由Qiuly发布

Code:

Qiuly

0 条评论

发表回复 取消回复

发表回复取消回复