题解 [ABC334F] Christmas Present 2

· · 题解

有一定难度的 ABC F。

题意

翻译很清楚。

标签：动态规划、线段树。

分析

设 f_i 表示到第 i 个点后回到原点（即 0 号）的最小距离。

在第 i 个点时，第 i-1 个点才回到原点，需要重新出发，即加上 0 号点到 i 号点的距离；而对于 \forall j \in[i-k,i-1)，这些点已经出发到了第 i-1 个点，即加上 i-1 号点到 i 号点的距离。

区间加和，区间查询，这个直接用线段树维护即可。

时间复杂度 O(n \log n)。

代码

//the code is from chenjh
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define MAXN 200002
using namespace std;
typedef long long LL;
typedef unsigned int ui;
using cu=const unsigned int;
int n,k;
int X[MAXN],Y[MAXN];
double dis(const int X1,const int Y1,const int X2,const int Y2){return sqrt((LL)(X1-X2)*(X1-X2)+(LL)(Y1-Y2)*(Y1-Y2));}//求两个坐标之间的距离。
#define lson (rt<<1)
#define rson (rt<<1|1)
double mn[MAXN<<2],lazy[MAXN<<2];//线段树维护最小值。
void pd(cu rt,cu l,cu r){
    mn[lson]+=lazy[rt],lazy[lson]+=lazy[rt];
    mn[rson]+=lazy[rt],lazy[rson]+=lazy[rt];
    lazy[rt]=0;
}
void update(cu rt,cu l,cu r,cu L,cu R,const double&val){
    if(L<=l && r<=R){mn[rt]+=val,lazy[rt]+=val;return;}
    pd(rt,l,r);
    ui mid=(l+r)>>1;
    if(L<=mid) update(lson,l,mid,L,R,val);
    if(mid<R) update(rson,mid+1,r,L,R,val);
    mn[rt]=min(mn[lson],mn[rson]);
}
double query(cu rt,cu l,cu r,cu L,cu R){
    if(L<=l && r<=R) return mn[rt];
    pd(rt,l,r);
    ui mid=(l+r)>>1;
    double ret=1e18;
    if(L<=mid) ret=min(ret,query(lson,l,mid,L,R));
    if(mid<R) ret=min(ret,query(rson,mid+1,r,L,R));
    return ret;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<=n;i++) scanf("%d%d",&X[i],&Y[i]);
    for(int i=1;i<=n;i++){
        if(i>1) update(1,0,n,max(i-k,0),i-2,dis(X[i-1],Y[i-1],X[i],Y[i]));//回到原点后又出发的点，
        update(1,0,n,i-1,i-1,dis(X[0],Y[0],X[i],Y[i]));//才回到原点的再出发。
        update(1,0,n,i,i,query(1,0,n,max(i-k,0),i-1)+dis(X[0],Y[0],X[i],Y[i]));//寻找距离最小值然后回到原点。
    }
    printf("%.6lf\n",query(1,0,n,n,n));
    return 0;
}