[yukicoder] No. 838 Noelちゃんと星々3

問題

方針

\( Y \) を昇順にソートさせてから考えます。

コストの計算

\( N = 2 \) のときは、どちらの高さに揃えてもコストは変わりません。\( N = 3 \) のときは、\( Y_2 \) に揃えることが最適です。これは、絶対偏差の和の最小化は中央値が最適であるためです。次に、\( d_i \) を \( i \) まで調べた時の距離の総和の最小値とすると、

\begin{eqnarray}
d_1 &=& \infty\\\
d_2 &=& |Y_2 – Y_1| \\
d_3 &=& |Y_2 – Y_1| + |Y_3 – Y_2|
\end{eqnarray}

となります。ここで、\( f(Y_i, Y_{i+1}, \cdots , Y_j) \) \( i \) から \( j \) までのグループの移動距離の総和の最小値とします。また、\( f(Y_i) = \infty\) とします。\( N = 4 \) のときを考えると、同じ高さのグループは、\( (Y_1, Y_2, Y_3, Y_4)\) または、\( (Y_1, Y_2), (Y_3, Y_4)\) となることが分かります。前者のグループについて、

\[f(Y_1, Y_2, Y_3, Y_4) = |Y_2 – Y_1| + |Y_3 – Y_2| + |Y_4 – Y_2|\]

となり、後者のグループでは、

\[ f(Y_1, Y_2) + f(Y_3, Y_4) = |Y_2 – Y_1| + |Y_4 – Y_3|\]

となります。\( |Y_4 – Y_3| \leq |Y_4 – Y_2|\) なので、

\[d_4 = f(Y_1, Y_2) + f(Y_3, Y_4)  \leq f(Y_1, Y_2, Y_3, Y_4)\]

となります。つぎに、\( N = 5\) について考えます。グループの分け方は、\( (Y_1, Y_2, Y_3, Y_4, Y_5) \)または、\( (Y_1, Y_2, Y_3), (Y_4, Y_5)\) または、\( (Y_1, Y_2), (Y_3, Y_4, Y_5)\) となりますが、グループのサイズが \( 4 \) 以上のものはさらに分解できるので、最初のグループは不適であることが分かります。

動的計画法

以上の議論から次の遷移式が導けます。

\[d_i = \min(d_{i-3} + |Y_{i-1} – Y_{i-2}| + |Y_{i} – Y_{i-1}|, d_{i-2} + |Y_{i} – Y_{i-1}|)\]

これは、\( i \) 個目の星を \( i -1 \) 個目の星の高さと同じにするか、\( i-2\) と \( i-1\) 個目の星の高さにするという操作を考えています。

コード

提出したコード

動的計画法