小蒟蒻想不出 $O(n)$ 的解法，来交一发二维 dp 加优化的题解。
Problem
圣诞老人要按顺序给 $n$ 个人送礼物，每个人（包括它自己）家都有一个坐标，而圣诞老人手上最多只能拿 $k$ 个礼物（这就意味着他可能要在送完某些人之后回家补充礼物），求他给所有人送完礼物再回到自己家所需要走的最短距离。
Solution
考虑 $dp_{i, j}$ 表示当前已经送完了前 $i$ 个人的礼物，（送完第 $i$ 个人之后）手上还有 $j$ 个礼物，当前在第 $i$ 个人的家中，需要走的最短路程。
我们用 $dis(a, b)$ 表示第 $a, b$ 个人的家之间的距离，其中第 $0$ 个人是圣诞老人。
同时，一个数组的下标为负数 $-i$，表示这个数组的倒数第 $i$ 个元素。
为了方便，我们认为圣诞老人每次补充礼物都会将礼物数量补充到 $k$ 个。
1. 初值
对于任意 $1 \le i \le n, 1 \le j \le k$ 有 $dp_{i, j} = +\infty$。
另外，$dp_{1, k - 1} = dis(0, 1)$。
2. 递推
在前往第 $i$ 个人家送礼物时，有两种选择：
- 直接从第 $i - 1$ 个人家去送，此时对于任意 $1 \le j \le k - 1$ 有：
$$dp_{i, j - 1} = \min(dp_{i, j - 1}, dp_{i - 1, j} + dis(i - 1, i))$$ - 先回家补充礼物再去送，此时对于任意 $0 \le j \le k - 1$ 有：
$$dp_{i, k - 1} = \min(dp_{i, k - 1}, dp_{i - 1, j} + dis(i - 1, 0) + dis(0, i))$$
注：
- 这里的 $j$ 表示上一次送完礼物后（即在送本次礼物之前），手上还有的礼物数量。
- 当 $j = 0$ 时，必须先回家补充礼物（这不是废话吗）。
3. 答案
由于我们增加了「我们认为圣诞老人每次补充礼物都会将礼物数量补充到 $k$ 个」这一限制，所以在计算答案时需要枚举所有可能的礼物数量，取路程的最小值，最后加上圣诞老人回家的路程，即
$$ans = (\min_{j = 0}^{k - 1} dp_{n, j}) + dis(n, 0)$$
4. 优化
现在我们的这个算法的复杂度为 $O(nk)$，显然是会超时的（当然还有内存超限，但是用个滚动数组就可以解决），于是我们要考虑一下优化方法。
我们发现，（在 $i$ 相等时）当存在剩余礼物比当前更多，而所需的最小路程比当前更小或相等时，我们没有必要对其最小路程进行计算，因为我们已经可以确定当前方案一定不是最优的方案。
所以我们设定数组 $v_i$ 来从大到小（请记住这一性质，后续优化会用到）存储送完前 $i$ 个人后，可能是最优方案的剩余礼物数 $j$。
换句话说，只有 $dp_{i, v_{i, 1}}, dp_{i, v_{i, 2}}, \cdots, dp_{i, v_{i, -1}}$ 可能是最优的答案，所以对于下一次的递推我们也只对 $v_i$ 中的 $j$ 进行递推。
特别地，$v_1 = \{k - 1\}$。
为了实现这个优化，我们在更新 $dp_i$ 时需按照 $j$ 从大到小的顺序进行更新。
关于数组 $v_i$ 的具体求法，请参考代码。
接下来我们又要回到最开始的问题上：初值。
为什么要在这个时候考虑初值的问题呢？我们在上面提到了：
当然还有内存超限，但是用个滚动数组就可以解决
于是这样就出现了一个新的问题：如果对于每个 $i$，都要对 $dp_i$ 中的所有位置赋初值 $+\infty$，那么时间复杂度不就又变成了 $O(nk)$ 吗？
要解决这个问题，我们需要考虑我们对 $dp$ 数组的更新。
我们再次回到上文。（省略了一些无关紧要的部分，下同）
- ……，此时对于任意 $1 \le j \le k - 1$ 有：
$$dp_{i, \color{red}{j - 1}} = \cdots$$- ……，此时对于任意 $0 \le j \le k - 1$ 有：
$$dp_{i, \color{red}{k - 1}} = \cdots$$
请注意上面的标红部分。可以发现，对于所有 $1 \le j \le k - 1$，$dp_{i, j - 1}$ 只会被更新一次，只有 $dp_{i, k - 1}$ 会被更新多次。
所以我们只需要对 $dp_{i, k - 1}$ 设置初值 $+\infty$ 即可。
（下面是一个很小的优化，如果不加不会对时间复杂度构成太大的影响，但还是希望各位看一下，代码中也加上了这个优化）
但是，真的到此为止了吗？
我们对于第二种情况的状态转移方程是：
- ……，此时对于任意 $0 \le j \le k - 1$ 有：
$$dp_{i, k - 1} = \min(dp_{i, k - 1}, dp_{i - 1, j} + dis(i - 1, 0) + dis(0, i))$$
我们可以将这里的状态转移方程改写为：
$$dp_{i, k - 1} = \min(dp_{i, k - 1}, (\min_{j = 0}^{k - 1} dp_{i - 1, j}) + dis(i - 1, 0) + dis(0, i))$$
而对于最小的 $dp_{i, j}$，一定有 $j$ 最小，因为比它更小的一定会被排除，不会用于本轮更新。
所以我们可以得到：
$$dp_{i, k - 1} = \min(dp_{i, k - 1}, dp_{i - 1, v_{i - 1, -1}} + dis(i - 1, 0) + dis(0, i))$$
于是，我们把 $dp_{i, k - 1}$ 的更新也减少到了 $1$ 次。
加了这三个优化后，代码跑得飞快，最慢的点只需约 $115\text{ms}$ 即可通过此题。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int infi = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3fll;
#define elif else if
#define il inline
int n, k;
ll sx, sy;
ll x[200005], y[200005];
double dp[2/*200005*/][200005]; // dp[i][j] 表示送完前i个人，手上还有j礼物，最少要走多远（当前在i号人的家中）
vector<int> v[2/*200005*/]; // v[i] 表示送完前i个人，只可能剩多少个礼物（如果被完爆，即当存在剩下礼物更多，而走的路可以更少或相同时，就不计入）
double dis(ll x1, ll y1, ll x2, ll y2)
{
return sqrtl((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int main()
{
cin >> n >> k >> sx >> sy;
for (int i = 1; i <= n; i++)
cin >> x[i] >> y[i];
dp[1][k - 1] = dis(sx, sy, x[1], y[1]);
v[1].push_back(k - 1);
for (int i = 2; i <= n; i++)
{
double mnd = infl; // 目前剩余礼物比j多的情况中，最少需要走多少路
dp[i % 2][k - 1] = infl;
v[i % 2].clear();
// 当前有j个礼物，在(x[i-1],y[i-1])
// 如果先回家拿
int j = v[(i - 1) % 2].back(); // 剩余礼物最少的，走的路一定是最少的，因为如果走的路更多一定会被排除
dp[i % 2][k - 1] = min(dp[i % 2][k - 1], dp[(i - 1) % 2][j] + dis(x[i - 1], y[i - 1], sx, sy) + dis(sx, sy, x[i], y[i]));
mnd = min(mnd, dp[i % 2][k - 1]);
v[i % 2].push_back(k - 1);
// 如果直接从这里去送
for (auto j : v[(i - 1) % 2])
if (j > 0) // 必须还有礼物才行，不然没礼物送了
{
dp[i % 2][j - 1] = dp[(i - 1) % 2][j] + dis(x[i - 1], y[i - 1], x[i], y[i]);
if (mnd > dp[i % 2][j - 1]) // 如果剩余礼物更少，走的路却没有更少，就被“完爆”了，一定不是最优
v[i % 2].push_back(j - 1);
mnd = min(mnd, dp[i % 2][j - 1]);
}
}
double ans = infl;
for (auto j : v[n % 2])
ans = min(ans, dp[n % 2][j]);
cout << fixed << setprecision(15) << ans + dis(x[n], y[n], sx, sy) << endl; // 最后还要回家
return 0;
}