题目链接：P3195 [HNOI2008] 玩具装箱 - 洛谷。
本题是经典 DP 斜率优化题型。
题目描述
P 教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。
P 教授有编号为 $1 \cdots n$ 的 $n$ 件玩具，第 $i$ 件玩具经过压缩后的一维长度为 $C_i$。
为了方便整理，P 教授要求：
- 在一个一维容器中的玩具编号是连续的。
- 同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物。形式地说，如果将第 $i$ 件玩具到第 $j$ 个玩具放到一个容器中，那么容器的长度将为 $x=j-i+\sum\limits_{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
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 \le j < i}\set{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)$。
该解法的时间复杂度为 $\Theta(n^2)$，无法通过本题。
DP 斜率优化
状态转移方程可转化为：
$$ f(i) = \min_{0 \le j < i}\set{f(j) + (i - (j + 1) + s_i - s_{j} - L)^2}\ = \min_{0 \le j < i}\set{f(j) + (s_i + i - (s_j + j) - (L+1))^2} \ = \min_{0 \le j < i}\set{f(j) + (t_i - t_j - (L+1))^2} \ = \min_{0 \le j < i}\set{f(j) + t_i^2 + t_j^2 + (L+1)^2 - 2t_it_j - 2t_i(L+1) + 2t_j(L+1)} \ $$
其中，$t_i = s_i + i$。
将与 $j$ 无关的项移到等式左边：
$$ f(i) - t_i^2 + 2t_i(L+1) - (L+1)^2 = \min_{0 \le j < i}\set{f(j) + t_j^2 + 2t_j(L+1-t_i)} $$
使用线性规划的思路来处理方程：考虑一次函数的斜截式 $y = kx + b$，将其移项得到 $b = y - kx$。我们将与 $j$ 有关的信息表示为 $y$ 的形式，把同时与 $i,j$ 有关的信息表示为 $kx$，把要最小化的信息（与 $f(i)$ 有关的信息）表示为 $b$，也就是截距。具体地，令 $$ \begin{align*} 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{align*} $$
则转移方程就写作 $b_i = \min_{j < i}\set{ 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 的复杂度优化到了 $\Theta(n)$。
