一道神奇的 斜率优化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)$。
然后考虑优化,运用排除法:单调队列、斜率优化。
于是考虑斜率优化。
- 化简式子:
进行移项
$$\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$。 - 分析
分析得出,我们实际上是要使得 $b$ 最小化,于是维护一个下凸包即可。但是发现本题中 $x=-\frac{1}{2\sqrt{r_j}}$ 不单调,所以用神奇方法(下文介绍)维护即可。
代码
维护凸包方法有很多:
- 不维护,考虑基于时间的分治算法(\(\texttt{CDQ}\) 分治),将整个区间分为 $\log_2n$ 个凸包,一一求解即可,然后向归并排序一样合并,时间复杂度为 $\Theta(n\log_2^2n)$。
- \(\texttt{Splay}\)+二进制分组,时间复杂度为 $\Theta(n\log_2^2n)$。
- 李超线段树,时间复杂度为 $\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; }
近期评论