简介
前置知识：凸包以及如何求凸包。
考虑线性动态规划的一类转移，可以整理为以下形式：
\[dp_i=\min/\max\{f_1(i)+f_2(j)+g(i) \cdot h(j)\}, j<i
\]
其中，\(f_1(i)\) 为仅关于 \(i\) 的某些信息的多项式，\(f_2(j)\) 为仅关于 \(j\) 的某些信息的多项式；\(g(i) \cdot h(j)\) 是两个这样的多项式的乘积。
根据情况的不同，这一类转移可以通过斜率优化进一步优化到 \(O(n \sim n \log^2 n)\) 的复杂度。
例题：P3195 [HNOI2008] 玩具装箱
一句话题意：给定一个长度为 \(n\) 的数列 $c_i $和一个常数 \(L\)，要求把该数列划分成若干段，每段 \([l,r]\) 的代价为 \((r-l + \sum_{i=l}^{r} c_i - L)^2\)。求各段划分代价之和的最小值。
预处理 \(c_i\) 的前缀和 \(s_i\)，根据题意可以列出转移方程：
\[dp_i = \min_{j<i} \{(i-j-1+s_i-s_j-L)^2+dp_j\}
\]
令 \(S_i = s_i+i\)，\(L \gets L+1\)，则方程可以化为：
\[\begin{align}
dp_i&= \min_{j<i} \{(S_i-S_j-L)^2+dp_j\} \\
&= \min_{j<i}\{(S_j^2+dp_j)+2(S_i-L) \cdot S_j\}+(S_i-L)^2
\end{align}\]