サンタの家を出るときは、必ずプレゼントを \(K\) 個持っているとして良いです。

DP[n][x]=n番目の家にプレゼントを配った直後に、まだプレゼントをx個持っている状態で、それまでに余分に移動した距離の最小値

というDPを考えます。ここで「余分に移動した距離」とは、スタート後に一度もサンタの家に戻らずに家1から家nに順に訪れるときの移動距離と、実際の移動距離の差を表します。\(\min_x DP[N][x]\) が分かれば問題に答えることができます。

DPの遷移は、
\(DP[n+1][x]=DP[n][x+1]\)
\(DP[n+1][K]=\min_xDP[n][x]+\alpha_n\)
となります。（\(\alpha_n\) は、家nから家n+1に直接移動するときの距離と、サンタの家を経由するときの距離の差）
添字を適切に振り直すことで、nからn+1への遷移はin-placeに行うことができ、スライド最小値によりDP[n][*]のminを持つことでO(1)で行えます。よって、全体でO(N)で問題に答えることができます。