[yukicoder] No. 838 Noelちゃんと星々3
問題
https://yukicoder.me/problems/no/838方針
\( 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\) 個目の星の高さにするという操作を考えています。
コード
提出したコード
https://yukicoder.me/submissions/352473動的計画法
ll dp[N + 1]{};
dp[0] = pow(10, 15);
dp[1] = abs(Y[1] - Y[0]);
dp[2] = abs(Y[1] - Y[0]) + abs(Y[2] - Y[1]);
for (int i = 3; i < N; i++) {
ll c1 = abs(Y[i-1] - Y[i - 2]) + abs(Y[i] - Y[i - 1]);
ll c2 = abs(Y[i - 1] - Y[i]);
dp[i] = min(dp[i-3] + c1, dp[i-2] + c2);
}