以下、子供 \(i\) の家のことを単に家 \(i\) と表記します。各 \(1\leq i < N\) について、子供 \(i\) にプレゼントを配ってから子供 \(i+1\) にプレゼントを配るまでの移動として考えるべきは以下の \(2\) 通りのみです。

• 家 \(i\) から家 \(i+1\) へ直接向かう。
• 家 \(i\) から一度サンタさんの家に戻ってプレゼントを補充したあと、そこから家 \(i+1\) へ向かう。

後者の移動を選択する \(i\) の集合に（便宜上）\(0, N\) を追加して得られる集合の要素を昇順に並べた列を \(t_1,t_2,\dots,t_l\) とします。このとき、「サンタさんは同時に \(K\) 個までしかプレゼントを持てない」という条件は、「各 \(1 \leq j < l\) について、\(t_{j+1}-t_j <= K\)」という条件と同値です。よって、上述した \(2\) 通りの移動における後者の移動距離から前者の移動距離を引いたものを \(d_i\) とおくと、本問題は以下のような問題に帰着されます。

• 実数列 \(d_1,d_2,\dots,d_{N-1}\) が与えられる。ここから、選んだ項同士の間隔が \(K\) を超えないようにいくつかの項を選ぶとき、選んだ項の総和の最小値を求めよ。

これは、\(\mathrm{dp}[i]=\) 「\(i\) 番目までの項から、\(i\) 番目を含むいくつかの項を間隔が \(K\) を超えないように選ぶとき、選んだ項の総和の最小値」と定義すると、\(\mathrm{dp}[i]\) の値を求めるのに必要な値は基本的には \(\mathrm{dp}[i-K], \mathrm{dp}[i-K+1],\dots, \mathrm{dp}[i-1]\) の最小値なので、segment tree やスライド最小値などを用いて \(O(N \log N)\) ないしは \(O(N)\) の計算量でこの問題を解くことができます。

実装例 (C++) :

#include <bits/stdc++.h>
#include <atcoder/segtree>

using namespace std;
using namespace atcoder;

using ll = long long;

double dist(int x1, int y1, int x2, int y2) {
    int dx = x2 - x1;
    int dy = y2 - y1;
    return sqrt((ll) dx * dx + (ll) dy * dy);
}

using S = double;

S op(S a, S b) { return min(a, b); }

S e() { return 1e18; }

int main() {
    int n, k, sx, sy;
    cin >> n >> k >> sx >> sy;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
    x.push_back(sx), y.push_back(sy);
    double ans = dist(sx, sy, x[0], y[0]);
    vector<double> d(n);
    for (int i = 0; i < n; i++) {
        double dir = dist(x[i], y[i], x[i + 1], y[i + 1]);
        double ret = dist(x[i], y[i], sx, sy) + dist(sx, sy, x[i + 1], y[i + 1]);
        ans += dir;
        d[i] = ret - dir;
    }
    segtree<S, op, e> dp(n + 1);
    dp.set(0, 0);
    for (int i = 1; i <= n; i++) {
        dp.set(i, dp.prod(max(0, i - k), i) + d[i - 1]);
    }
    ans += dp.get(n);
    cout << fixed << setprecision(15) << ans << endl;
}