P3195 [HNOI2008] 玩具装箱

题目链接：P3195 [HNOI2008] 玩具装箱 - 洛谷。

本题是经典 DP 斜率优化题型。

题目描述

P 教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。

P 教授有编号为 $1 \dots n$ 的 $n$ 件玩具，第 $i$ 件玩具经过压缩后的一维长度为 $C_{i}$ 。

为了方便整理，P 教授要求：

在一个一维容器中的玩具编号是连续的。
同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物。形式地说，如果将第 $i$ 件玩具到第 $j$ 个玩具放到一个容器中，那么容器的长度将为 $x = j - i + \sum_{k = i}^{j} C_{k}$ 。

制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为 $x$ ，其制作费用为 $(x - L)^{2}$ 。其中 $L$ 是一个常量。P 教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 $L$ 。但他希望所有容器的总费用最小。

输入格式

第一行有两个整数，用一个空格隔开，分别代表 $n$ 和 $L$ 。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数代表第 $i$ 件玩具的长度 $C_{i}$ 。

输出格式

输出一行一个整数，代表所有容器的总费用最小是多少。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

对于全部的测试点， $1 \leq n \leq 5 \times 10^{4}$ ， $1 \leq L \leq 10^{7}$ ， $1 \leq C_{i} \leq 10^{7}$ 。

题解

参考文档：斜率优化 - OI Wiki

状态定义和转移

定义 $f (i)$ 为前 $i$ 个物品收纳的最小费用。

边界条件：

f (0) = 0

状态转移方程：

f (i) = min_{0 \leq j < i} {f (j) + p (j + 1, i)}

其中， $p (l, r)$ 表示将区间 $[l, r]$ 装到同一个容器的代价。

p (l, r) = (r - l + \sum_{k = l}^{r} C_{k} - L)^{2} = (r - l + s_{r} - s_{l - 1} - L)^{2}

其中， $s_{i}$ 表示 $C_{i}$ 的前缀和。

最终答案即为 $f (1, n)$ 。

该解法的时间复杂度为 $Θ (n^{2})$ ，无法通过本题。

DP 斜率优化

状态转移方程可转化为：

f (i) = min_{0 \leq j < i} {f (j) + (i - (j + 1) + s_{i} - s_{j} - L)^{2}}

其中， $t_{i} = s_{i} + i$ 。

将与 $j$ 无关的项移到等式左边：

f (i) - t_{i}^{2} + 2 t_{i} (L + 1) - (L + 1)^{2} = min_{0 \leq j < i} {f (j) + t_{j}^{2} + 2 t_{j} (L + 1 - t_{i})}

使用线性规划的思路来处理方程：考虑一次函数的斜截式 $y = k x + b$ ，将其移项得到 $b = y - k x$ 。我们将与 $j$ 有关的信息表示为 $y$ 的形式，把同时与 $i, j$ 有关的信息表示为 $k x$ ，把要最小化的信息（与 $f (i)$ 有关的信息）表示为 $b$ ，也就是截距。具体地，令

\begin{aligned} x_{j} & =t_{j} \\ y_{j} & =f(j)+t_{j}^{2} \\ k_{i} & =-2(L+1-t_{i}) \\ b_{i} & =f(i)-t_{i}^{2}+2t_{i}(L+1)-(L+1)^{2} \end{aligned}

则转移方程就写作 $b_{i} = min_{j < i} {y_{j} - k_{i} x_{j}}$ 。我们把 $(x_{j}, y_{j})$ 看作二维平面上的点，则 $k_{i}$ 表示直线斜率， $b_{i}$ 表示一条过 $(x_{j}, y_{j})$ 的斜率为 $k_{i}$ 的直线的截距。问题转化为：选择合适的 $j$ （ $1 \leq j < i$ ），最小化直线的截距。

如图，我们将这个斜率为 $k_{i}$ 的直线从下往上平移，直到有一个点 $(x_{p}, y_{p})$ 在这条直线上，则有 $b_{i} = y_{p} - k_{i} x_{p}$ ，这时 $b_{i}$ 取到最小值。算完 $f (i)$ 后，我们就把 $(x_{i}, y_{i})$ 这个点加入点集中，以做为新的 DP 决策。那么，我们该如何维护点集？

容易发现，可能让 $b_{i}$ 取到最小值的点一定在下凸壳上。因此在寻找 $p$ 的时候我们不需要枚举所有 $i - 1$ 个点，只需要考虑凸包上的点。而在本题中 $k_{i}$ 随 $i$ 的增加而递增，因此我们可以单调队列维护凸包。

具体地，设 $K (a, b)$ 表示过 $(x_{a}, y_{a})$ 和 $(x_{b}, y_{b})$ 的直线的斜率。考虑队列 $q_{l}, q_{l + 1}, \dots, q_{r}$ ，维护的是下凸壳上的点。显然下凸壳上的斜率 $K (a, b)$ 是单增的，即，对于 $l < i < r$ ，始终有 $K (q_{i - 1}, q_{i}) < K (q_{i}, q_{i + 1})$ 成立。

我们维护一个指针 $e$ 来计算 $b_{i}$ 最小值。我们需要找到一个 $K (q_{e - 1}, q_{e}) \leq k_{i} < K (q_{e}, q_{e + 1})$ 的 $e$ （特别地，当 $e = l$ 或者 $e = r$ 时要特别判断），这时就有 $p = q_{e}$ ，即 $q_{e}$ 是 $i$ 的最优决策点。由于 $k_{i}$ 是单调递增的，因此 $e$ 的移动次数是均摊 $O (1)$ 的。

在插入一个点 $(x_{i}, y_{i})$ 时，我们要判断是否 $K (q_{r - 1}, q_{r}) < K (q_{r}, i)$ ，如果不等式不成立就将 $q_{r}$ 弹出，直到等式满足。然后将 $i$ 插入到 $q$ 队尾。

这样我们就将 DP 的复杂度优化到了 $Θ (n)$ 。