M - シリーズ / series Editorial by Tomii9273
遅延評価セグ木上でDPをする解法便宜上、\(i\) 巻のみを \(A_i\) 円で買う買い方も「巻数 \(1\) のセット買い」と見なし、合計 \((M+N)\) 種類のセットがあるものとします。
\(DP[i]\) を「\(i\) 巻目以下の全巻を入手するための最小の金額」とします。このとき、
\(DP[i] =
\begin{cases}
0 & (i=0)\\
\displaystyle\min_{L_j \leq i \leq R_j} (DP[L_j - 1] + B_j) & (i \geq 1)
\end{cases}\)
であるため、\(i\) が小さい側から求めていくことで \(DP[i]\) をすべて求められます。
これを「渡す DP」で考えると、\(L_j\) が小さい順に各セットについて以下の区間更新操作を行えばよいことが分かります。
- \(DP[L_j], \ldots, DP[R_j]\) を \(DP[L_j-1] + B_j\) との最小値に更新する
これは、\(DP\) を遅延評価セグメント木とすることで、時間計算量 \(O((N+M)\log N)\) で実現できます。
posted:
last update: