問題

提出解答

解法

座標平面上の点 $S, P_i~(i=1,2, \dots, N)$ を $S = (S_X, S_Y), P_i = (X_i, Y_i)$ とする.

動的計画法で解く. $i = 1, 2, \dots, N+1$ に対して, ${\rm DP}(i)$ で, 問題を $P_i, P_{i+1}, \dots, P_N$ へ制限したときの距離の総和の最小値とする. このとき, 最終解答は ${\rm DP}(1)$ になる.

ベースケースは $i = N + 1$ のときで, このとき, 経由すべき点がないことから, 移動が発生しないので, ${\rm DP}(N + 1) = 0$ である.

遷移式を考える. $i$ のときに, 連続して配るプレゼントの個数 $k$ で場合分けをする. 連続して $k$ 個配る場合における距離の総和を最小化する移動の方法は, 以下の手順をたどることになる.

点 $S$ から点 $P_i$ へ移動.
$j = 1,2, \dots, k - 1$ に対して, 点 $P_{i+j-1}$ から $P_{i+j}$ へ移動.
点 $P_{i + k - 1}$ から点 $S$ へ移動.
それ以降は ${\rm DP}(i + k)$ を達成するように移動する.

よって, この場合における距離の総和の最小値は

$\displaystyle \operatorname{dist}(S, P_i) + \sum_{j = 1}^{k - 1} \operatorname{dist}(P_{i + j - 1}, P_{i + j}) + \operatorname{dist}(P_{i + k - 1}, S) + {\rm DP}(i + K)$

となる.

これを $k$ について動かすことによって, ${\rm DP}(i)$ の値は

$\displaystyle \begin{align*} {\rm DP}(i) &= \displaystyle \min_{\substack{1 \leq k \leq K \\ i + k \leq N + 1}} \left( \operatorname{dist}(S, P_i) + \sum_{j = 1}^{k - 1} \operatorname{dist}(P_{i + j - 1}, P_{i + j}) + \operatorname{dist}(P_{i + k - 1}, S) + {\rm DP}(i + k) \right) \\ &= \displaystyle \operatorname{dist}(S, P_i) + \min_{\substack{1 \leq k \leq K \\ i + k \leq N + 1}} \left(\sum_{j = 1}^{k - 1} \operatorname{dist}(P_{i + j - 1}, P_{i + j}) + \operatorname{dist}(P_{i + k - 1}, S) + {\rm DP}(i + k) \right) \end{align*}\$

となる.

ここで, $T(i + k) := \operatorname{dist}(P_{i + k - 1}, S) + {\rm DP}(i + k)$ とおくことにすると,

$\displaystyle {\rm DP}(i) = \operatorname{dist}(S, P_i) + \min_{\substack{1 \leq k \leq K \\ i + k \leq N + 1}} \left(\sum_{j = 1}^{k - 1} \operatorname{dist}(P_{i + j - 1}, P_{i + j})+ T(i + k) \right)$

となる.

また, $1 \leq l \leq r \leq N$ に対して,

$\displaystyle U_{l,r} := \sum_{t = l + 1}^r \operatorname{dist}(P_{t - 1}, P_t)$

とおくことにすると,

$\displaystyle {\rm DP}(i) = \operatorname{dist}(S, P_i) + \min_{\substack{1 \leq k \leq K \\ i + k \leq N + 1}} \left( U_{i, i + k} + T(i + k) \right)$