本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-29 18:28:19

这道题大部分都是使用 dp 和单调队列去做的， 中间也需要前缀和来维护， 题解中也有一些讲解。
只是做的时候要注意是按 $1$ 到 $N$ 的顺序送礼物就可以了。

非正解

这里我们设圣诞老人家为 $0$ 号房间， $sum_i$ 为圣诞老人从 $0$ 号房间到 $1$ 号房间， 再到 $2$ 号， $3$ 号...... 直到 $i$ 号且中途不回自己家的距离，$m(i,j)$ 表示 $i$ 号房间到 $j$ 号房间的欧几里得距离， 下文公式中的 $i$ 表示圣诞老人所在的房间， $j$ 表示圣诞老人在送完 $i-j$ 号房间后回到自己家中。
易得公式：
$$f_i=\min(f_{i-j}+m(i-j+1,0)+sum_i-sum_{i-j+1}+m(i,0))(1\le j\le k)$$ 将与 $j$ 不相关的项移出函数， 得：
$$f_i=\min(f_{i-j}+m(i-j+1,0)-sum_{i-j+1})+sum_i+m(i,0)(1\le j\le k)$$ 所以我们只需枚举出 $f_{i-j}+m(i-j+1,0)-sum_{i-j+1}$ 的最小值即可。
时间复杂度为 $O(n^2)$， 明显超时。

正解

分析代码， 发现明显可以使用单调队列优化。
那么存入单调队列中的下标固然为 $i$， 值应将 $j$ 移出， 得 $f_i+m(i+1,0)-sum_{i+1}$， 我们用 $ans(i)$ 表示 。
那么我们设队首下标为 $l$， 则公式得：
$$f_i=ans(l)+sum_i+m(i,0)$$ 那如何处理队列为空的情况呢？
很简单， 在队列中放入一个 $0$ 即可。
时间复杂度为 $O(n)$。
代码：

#include<bits\/stdc++.h>
#define m(i,j) sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))
#define ans(i) f[i]+m(i+1,0)-sum[i+1]
using namespace std;
deque<int>d;
const int MAX=2*1e5+5;
long long n,k,x[MAX],y[MAX];
double sum[MAX],f[MAX];
void que(int l){
	while(!d.empty()&&d.front()+k<=l) d.pop_front();
	while(!d.empty()&&ans(d.back())>ans(l)) d.pop_back();
	d.push_back(l);
	return; 
} 
int main(){
	cin>>n>>k;
	for(int i=0;i<=n;i++) cin>>x[i]>>y[i];
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+m(i,i-1);
	d.push_back(0);
	for(int i=1;i<=n;i++){
		f[i]=ans(d.front())+m(i,0)+sum[i];
		que(i);
	}
	printf("%.15lf",f[n]);
	return 0;
}