警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「HNOI 2008」玩具装箱 - 斜率优化 + DP

题意

传送门:洛谷 P3195 - 玩具装箱

给你一个序列 \(a\)。你要把它分成若干段。区间 \([l, r]\) 的代价是 \([ \left( r - l - 1 + \sum_{i=l}^r a_i \right) - L]^2\)。最小化代价和。

解法

首先这显然是道 DP 题。

\(dp_i\)\([1, i]\) 的最小代价和。那么我们可以得到下面的方程:

\[dp_i = \min_{0 \le j < i} \left\{ dp_j + \left[ \left( i - j - 1 + \sum_{k=j+1}^i a_k \right) - L \right]^2 \right\}\]

我们又令 \(s_i = \sum_{j=1}^i a_j\),那么方程可以化成:

\[dp_i = \min_{0 \le j < i} \left\{ dp_j + \left( i - j - 1 + s_i - s_j - L \right)^2 \right\}\]

这个式子转移是 \(O(n)\) 的,DP 复杂度会达到 \(O(n^2)\)。考虑优化。

我们令 \(A_i = s_i + i, B_i = s_i + i + L + 1\)。那么式子可以写成:

\[dp_i = \min_{0 \le j < i} \left\{ dp_j + \left( A_i - B_j \right)^2 \right\}\]

假设我们在计算 \(dp_i\),且有两个决策 \(x, y\) 满足 \(\mathbf{x > y}\)\(\mathbf{x}\) 优于 \(\mathbf{y}\)。即 \(dp_x + (A_i - B_x)^2 < dp_y + (A_i - B_y)^2\)。我们可以将这个式子进行下面的变形: \[ \begin{align*} dp_x + (A_i - B_x)^2 & < dp_y + (A_i - B_y)^2 \\ dp_x + A_i^2 - 2A_iB_x + B_x^2 & < dp_y + A_i^2 - 2A_iB_y + B_y^2 \\ \left(dp_x + B_x^2\right) - \left(dp_y + B_y^2\right) & < 2A_i(B_x - B_y) \\ \frac {\left(dp_x + B_x^2\right) - \left(dp_y + B_y^2\right)} {B_x - B_y} & < 2A_i \\ \end{align*} \] 我们又双叒叕\(\operatorname{slope}(x, y)\)\(\frac {\left(dp_x + B_x^2\right) - \left(dp_y + B_y^2\right)} {B_x - B_y}\)

那么我们可以维护一个单调队列,使得从队尾到队首,\(\operatorname{slope}(x+1, x)\) 递增,保证队首决策最优。每次决策从队首转移。因为每个元素入队出队次数都是 \(O(1)\) 的,且转移复杂度也是 \(O(1)\),所以总复杂度为 \(O(n)\)

代码