H - Histogram Editorial by kyopro_friends
\(A\) は単調増加になるようソートされているとして構いません。
公式解説と同様の考察により、操作後の配列の値を \(A'\) とすると、最適解においては、あるインデックスの列 \(0=P_0<\ldots<P_K=N\) が存在して、全ての
\(i\) について \(P_{k-1}<i\leq P_{k}\Rightarrow A'_i=A_{P_k}\) が成り立ちます。
したがって、操作をそのようなものに限って考えて構いません。
(操作のイメージ)
\(dp[i]=\)\(A_1\) から \(A_i\) までだけを考慮したときの最小コスト
とすると、求める答えは \(dp[N]\) になります。
\(A_i\) からさかのぼってどこまでを同じ値にするか考えることで、
\(dp[i]=\min_{0\leq j<i}(dp[j]+X+\sum_{j<k\leq i}(A_i-A_k)C_k)\)
となります。これを高速に計算することを考えましょう。
\(i\) の影響をできるだけminの外に出すことを考えます。
ここで、\(C\) の累積和を \(D\)、\(AC\) の累積和を \(E\) とします。正確には
\(D_i=\sum_{1\leq j\leq i}C_j\)
\(E_i=\sum_{1\leq j\leq i}A_jC_j\)
とします。(ただし、\(D_0=E_0=0\) と定める)
これを用いてDPの遷移式を変形すると
\(dp[i]=(D_iA_i-E_i)+\min_{0\leq j<i}(-D_jA_i+E_j+dp[j]+X)\)
となります。ここでminの中身は、係数が \(j\)
のみに依存する \(A_i\) の \(1\) 次式となります。
したがって Convex Hull Trick により、この min は \(O(\log N)\) で求めることができ、\(dp[N]\) は \(O(N\log N)\) で求めることができました。
今回は \(1\) 次の係数の単調性と \(A_i\) の単調性から、Convex Hull Trick 部分は \(O(N)\) で行うこともできます。(\(A\) をソートする部分がボトルネックとなり、全体の計算量は変わらず \(O(N\log N)\) になります)
posted:
last update: