一道神奇的 斜率优化DP 题。

题目链接：Luogu P2497/BZOJ 3006/SDOI2012 R2D1T3。

题目

题目描述

up 主家终于买电脑了，但是接下来有各种问题要处理。首要解决的问题就是网络问题。他要从移动公司开始，通过一些基站来传递网络到他家。

为了简化问题，我们假设移动公司，所有的基站，up 主家位于同一条直线上，他们都位于这一条直线上的某一点 $x$，这些点不会重合。每个基站发射和接收的范围都是一个切于地面的圆，发射的半径 $r_1$ 是固定的，接收半径 $r_2$ 是可调的的。如下图：

一个点 $i$ 如果能从另一个点 $j$ 接收到信号（当且仅当 $x_j$ 小于 $x_i$)。

必须满足 $i$ 的接收范围与 $j$ 的发射范围相切，并且需要付 $\sqrt{r _ {2,i}}$ 的额外费用。同时启动每一个点 $i$ 都需要费用 $v_i$。

当然一个点如果能够发射的 up 主家只需要这个点的发射范围与 up 主家所在的竖线相切或相交即可，如下图：

当然费用越少就越好咯，于是 up 主想要请你帮他的忙。

数据范围

$$1\leq n\leq 5 \times 10^6$$

$$x_i,m\leq 10^{12}$$

$$v_i\leq 10^4$$

时空限制

题目	时间限制	空间限制
Luogu P2497	$$13\text{s}$$	$$500\text{MiB}$$
BZOJ 3006	$$?\text{s}$$	$$?\text{MiB}$$
SDOI2012 R2D1T3	$$13\text{s}$$	$$512\text{MiB}$$

题解

思路

首先，我们要求出 $i,j$ 之间信号传递的代价。

所以根据勾股定理得到式子：

$$(r _ {2,i}+r _ {1,j})^2=(r _ {2,i}-r _ {1,j})^2+(x_i-x_j)^2$$

$$4r _ {2,i}\times r _ {1,j}=(x_i-x_j)^2$$

所以联通代价为 $\sqrt{r_{2,i}}=\frac{x_i-x_j}{2\sqrt{r_j}}$。

设 $\text{dp}_i$ 信号达到基站 $i$ 的最小代价，那么首先可以看出：

$$\text{dp}_1=v_1$$

$$\text{dp}_i=\min_{j\in[1,i-1]}(\text{dp}_j+\frac{x_i-x_j}{2\sqrt{r_j}})+v_i$$

发现这是一个简单的动态规划问题，上述式子的时间复杂度为 $\Theta(n^2)$。

然后考虑优化，运用排除法：单调队列、斜率优化。

于是考虑斜率优化。

1. 化简式子：
   进行移项
   $$\text{dp}_i-v_i-\frac{1}{2\sqrt{r_j}}\times x_i=\text{dp}_j-\frac{x_j}{2\sqrt{r_j}}$$
   然后设 $y=\text{dp}_j-\frac{x_j}{2\sqrt{r_j}}$，$k=x_i$，$x=-\frac{1}{2\sqrt{r_j}}$，$b=\text{dp}_i-v_i$。
2. 分析
   分析得出，我们实际上是要使得 $b$ 最小化，于是维护一个下凸包即可。但是发现本题中 $x=-\frac{1}{2\sqrt{r_j}}$ 不单调，所以用神奇方法（下文介绍）维护即可。

代码

维护凸包方法有很多：

1. 不维护，考虑基于时间的分治算法（\(\texttt{CDQ}\) 分治），将整个区间分为 $\log_2n$ 个凸包，一一求解即可，然后向归并排序一样合并，时间复杂度为 $\Theta(n\log_2^2n)$。
2. \(\texttt{Splay}\)+二进制分组，时间复杂度为 $\Theta(n\log_2^2n)$。
3. 李超线段树，时间复杂度为 $\Theta(n\log_2n)$。

下面就是李超线段树的版本。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
typedef double db;
#define eps 1e-12 //精度
#define INF 1e32 //正无穷
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline ll read(void){ //快读，记得开 long long
    reg bool f=false;
    reg char ch=getchar();
    reg ll res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=5000000+5;

struct Node{ //保存基站信息
    ll x,r;
    int v;
    inline void Read(void){
        x=read(),r=read(),v=read();
        return;
    }
};

int n;
ll m;
db dp[MAXN],ans;
Node a[MAXN];

struct SegmentTree{ //李超线段树
    #define mid ( ( (l) + (r) ) >> 1)
    struct Node{
        int son[2];
        db k,b;
    };
    int tot;
    Node unit[MAXN];
    inline db f(reg db x,reg db kk,reg db bb){
        return kk*x+bb;
    }
    inline void Query(reg ll l,reg ll r,reg int x,reg int y){
        if(x==0)
            return;
        dp[y]=min(dp[y],f(a[y].x,unit[x].k,unit[x].b));
        if(a[y].x<=mid)
            Query(l,mid,unit[x].son[0],y);
        else
            Query(mid+1,r,unit[x].son[1],y);
        return;
    }
    inline void Add(reg ll l,reg ll r,reg int x,db& k,db& b){
        if(x==0){
            ++tot;
            unit[tot].k=k;
            unit[tot].b=b;
            return;
        }
        reg bool fl=(f(l,k,b)-f(l,unit[x].k,unit[x].b)>eps);
        reg bool fr=(f(r,k,b)-f(r,unit[x].k,unit[x].b)>eps);
        reg bool fm=(f(mid,k,b)-f(mid,unit[x].k,unit[x].b)>eps);
        if((fl)&&(fr)&&(fm))
            return;
        if((!fl)&&(!fr)&&(!fm)){
            unit[x].k=k;
            unit[x].b=b;
            return;
        }
        reg bool s=(fm^fr);
        if(!fm){
            swap(unit[x].k,k);
            swap(unit[x].b,b);
        }
        if(s)
            Add(mid+1,r,unit[x].son[s],k,b);
        else
            Add(l,mid,unit[x].son[s],k,b);
        if(!unit[x].son[s])
            unit[x].son[s]=tot;
        return;
    }
    #undef mid
};

SegmentTree T;

int main(void){
    n=read(),m=read();
    a[1].Read(); //读入公司信息
    for(reg int i=2;i<=n;++i)
        a[i].Read(); //读入其他信息（其实完全没有必要把两个分开）
    T.unit[1].k=1/(sqrt((db)a[1].r)*2); //初始节点
    T.unit[1].b=(db)(-a[1].x)/(sqrt((db)a[1].r)*2)+a[1].v;
    dp[1]=a[1].v;
    T.tot=1; //动态开点
    for(reg int i=2;i<=n;++i){ //动态规划
        dp[i]=INF;
        T.Query(a[1].x,a[n].x,1,i);
        dp[i]+=a[i].v;
        db k=1/(sqrt((db)a[i].r)*2);
        db b=(db)(-a[i].x)/(sqrt((db)a[i].r)*2)+dp[i];
        T.Add(a[1].x,a[n].x,1,k,b);
    }
    ans=INF; //统计答案
    for(reg int i=1;i<=n;++i)
        if(a[i].x+a[i].r>=m) //题目已经保证基站一定在家的左边，没必要判断 x-r 与 m 的关系
            ans=min(ans,dp[i]);
    printf("%.3lf\n",ans); //输出答案
    return 0;
}