AIOJ

例题引入

「HNOI2008」玩具装箱

有 $n$ 个玩具排成一排，第 $i$ 个玩具价值为 $c_i$ ．要求将这 $n$ 个玩具分成若干段．对于一段 $[l,r]$ ，它的代价为 $(r-l+\sum_{i=l}^r c_i-L)^2$ ．其中 $L$ 是一个常量，求分段的最小代价．

$1\le n\le 5\times 10^4, 1\le L, c_i\le 10^7$ ．

朴素的 DP 做法

令 $f_i$ 表示前 $i$ 个物品，分若干段的最小代价．

状态转移方程：$f_i=\min_{j [!note]+ 玩具装箱改

有 $n$ 个玩具排成一排，第 $i$ 个玩具价值为 $c_i$ ．要求将这 $n$ 个玩具分成若干段．对于一段 $[l,r]$ ，它的代价为 $(r-l+\sum_{i=l}^r c_i-L)^2$ ．其中 $L$ 是一个常量，求分段的最小代价．

$1\le n\le 5\times 10^4,1\le L\le 10^7,-10^7\le c_i\le 10^7$ ．

本题与「玩具装箱」问题唯一的区别是，玩具的价值可以为负．延续之前的思路，令 $f_i$ 表示前 $i$ 个物品，分若干段的最小代价．

状态转移方程： $f_i=\min_{j<i}\{f_j+(pre_i-pre_j+i-j-1-L)^2\}$ ．

其中 $pre_i = \sum_{j=1}^i c_j$ ．

将方程做相同的变换

f_i - (s_i-L')^2=\min_{j<i}\{f_j+s_j^2 + 2s_j(L'-s_i) \}

然而这时有两个条件不成立了：

直线的斜率不再单调；
每次加入的决策点的横坐标不再单调．

仍然考虑凸壳的维护．

在寻找最优决策点，也就是用直线切凸壳的时候，我们将单调队列找队首改为：凸壳上二分．我们二分出斜率最接近直线斜率的那条凸壳边，就可以找到最优决策．

在加入决策点，也就是凸壳上加一个点的时候，我们有两种方法维护．

第一种方法是直接用平衡树维护凸壳．那么寻找决策点的二分操作就转化为在平衡树上二分，插入决策点就转化为在平衡树上插入一个结点，并删除若干个被踢出凸壳的点．此方法思路简洁但实现繁琐．

下面介绍一种基于 CDQ 分治的做法．

设 $\text{CDQ}(l,r)$ 代表计算 $f_i,i\in [l,r]$ ．考虑 $\text{CDQ}(1,n)$ ：

我们先调用 $\text{CDQ}(1,mid)$ 算出 $f_i,i\in[1,mid]$ ．然后我们对 $[1,mid]$ 这个区间内的决策点建凸壳，然后使用这个凸壳去更新 $f_i,i\in [mid+1,n]$ ．这时我们决策点集是固定的，不像之前那样边计算 DP 值边加入决策点，那么我们就可以把 $i \in [mid+1,n]$ 的 $f_i$ 先按照直线的斜率 $k_i$ 排序，然后就可以使用单调队列来计算 DP 值了．当然，也可以在静态凸壳上二分计算 DP 值．
对于 $[mid+1,n]$ 中的每个点，如果它的最优决策的位置是在 $[1,mid]$ 这个区间，在这一步操作中他就会被更新成最优答案．当执行完这一步操作时，我们发现 $[1,mid]$ 中的所有点已经发挥了全部的作用，凸壳中他们存不存在已经不影响之后的答案更新．因此我们可以直接舍弃这个区间的决策点，并使用 $\text{CDQ}(mid+1,n)$ 解决右区间剩下的问题．

时间复杂度 $O(n\log^2 n)$ ．

对比「玩具装箱」和「玩具装箱改」，可以总结出以下两点：

二分/CDQ/平衡树等能够优化 DP 方程的计算，于一定程度上降低复杂度，但不能改变这个方程本身．
DP 方程的性质会取决于数据的特征，但 DP 方程本身取决于题目中的数学模型．

小结

斜率优化 DP 需要灵活运用，其宗旨是将最优化问题转化为二维平面上与凸包有关的截距最值问题．遇到性质不太好的方程，有时需要辅以数据结构来加以解决，届时还请就题而论．

斜率优化

例题引入

朴素的 DP 做法

小结

习题