斜率优化dp——玩具装箱
分析：
状态转移方程：（显然）
dp[i]=min(dp[j]+(sum[i]-sum[j]+i-j-1-L)^2)dp[i]=min(dp[j]+(sum[i]−sum[j]+i−j−1−L)2)
sumsum 为前缀和
然后我们令 f[i]=sum[i]+i,c=1+Lf[i]=sum[i]+i,c=1+L
原式可以化简为：
dp[i]=min(dp[j]+(f[i]-f[j]-c)^2)dp[i]=min(dp[j]+(f[i]−f[j]−c)2)
注意，这里的 f,cf,c 都是可以预处理出来的
1.证明决策单调性
假设在当前由 jj 状态转移优于 kk 状态（显然 kk 是之前枚举的决策），即：
dp[j]+(f[i]-f[j]-c)^2\le dp[k]+(f[i]-f[j]-c)^2dp[j]+(f[i]−f[j]−c)2≤dp[k]+(f[i]−f[j]−c)2
那么对于 ii 后面的一个状态 tt ，要保证 kk 对其无贡献（已经被 jj 覆盖）
则需要证明：
dp[j]+(f[t]-f[j]-c)^2\le dp[k]+(f[t]-f[k]-c)^2dp[j]+(f[t]−f[j]−c)2≤dp[k]+(f[t]−f[k]−c)2
由于 f[i]=sum[i]+if[i]=sum[i]+i ，所以一定为单调递增的（ sumsum 和 ii 均为单调递增）
所以令 v=f[t]-f[i]v=f[t]−f[i]
原式可化为：
dp[j]+(f[i]+v-f[j]-c)^2\le dp[k]+(f[i]+v-f[k]-c)^2dp[j]+(f[i]+v−f[j]−c)2≤dp[k]+(f[i]+v−f[k]−c)2
变形↓尽量拆出已有的式子
dp[j]+(f[i]-f[j]-c)^2+2v*(f[i]-f[j]-c)+4v^2\le dp[k]+(f[i]-f[k]-c)^2+2v*(f[i]-f[k]-c)+4v^2dp[j]+(f[i]−f[j]−c)2+2v∗(f[i]−f[j]−c)+4v2≤dp[k]+(f[i]−f[k]−c)2+2v∗(f[i]−f[k]−c)+4v2
移项，消除相同项
f[i]-f[j]-c\le f[i]-f[k]-cf[i]−f[j]−c≤f[i]−f[k]−c
f[j]\ge f[k]f[j]≥f[k]
由单调递增性，只需要枚举状态时以 11 ~ i-1i−1 的顺序即可保证 f[j]\ge f[k]f[j]≥f[k] ，得证
2.求斜率方程
当前决策 ii ，若由 jj 状态转移优于 kk 状态，则有：
dp[j]+(f[i]-f[j]-c)^2\le dp[k]+(f[i]-f[j]-c)^2dp[j]+(f[i]−f[j]−c)2≤dp[k]+(f[i]−f[j]−c)2
展开，变形，得：
dp[j]+f[i]^2-2f[i]* (f[j]+c)+(f[j]+c)^2\le dp[k]+f[i]^2-2f[i]* (f[k]+c)+(f[k]+c)^2dp[j]+f[i]2−2f[i]∗(f[j]+c)+(f[j]+c)2≤dp[k]+f[i]2−2f[i]∗(f[k]+c)+(f[k]+c)2
移项，消除相同项，尽量将变量按 j,kj,k 凑在一起，得：
\frac {(dp[j]+(f[j]+c)^2)-(dp[k]+(f[k]+c)^2)}{2*(f[j]-f[k])}\le f[i]2∗(f[j]−f[k])(dp[j]+(f[j]+c)2)−(dp[k]+(f[k]+c)2)≤f[i]
左边部分就像斜率一样，可以看做：
\frac {Y_j-Y_k} {X_j-X_k}Xj−XkYj−Yk
我们以 Slope(x,y)Slope(x,y) 来表示上面那个类似于斜率的东西（其实就是斜率好么）
若满足这个 Slope(k,j)\le f[i]Slope(k,j)≤f[i] ，则说明 jj 比 kk 优
3.组织算法
那么对于当前较优的状态我们建立一个队列 qq
维护这个队列我们有以下操作：
1.若 Slope(q[l],q[l+1])\le f[i]Slope(q[l],q[l+1])≤f[i] ，则 q[l]q[l] 没有 q[l+1]q[l+1] 优，则删除 q[l]q[l] 2.若 Slope(q[r-1],q[r])\ge Slope(q[r],i)Slope(q[r−1],q[r])≥Slope(q[r],i) ,则删除 q[r]q[r]
分析：
方程成立时是 jj 比 kk 优的充分必要条件，那么假设我们现在有一个序列，那么队头就是当前最优的，若到了某个 ii 值使得对于队首 p[l]p[l]和队次首 p[l+1]p[l+1] 来说 Slope(q[l],q[l+1])\le f[i]Slope(q[l],q[l+1])≤f[i] 成立，则 q[l+1]q[l+1] 比 q[l]q[l] 优，所以弹出队首，直到不成立为止
第一条操作是显然的，那么第二条呢？
一个状态要不要放在序列里，是由它能不能做出贡献决定的，也就是说，它能不能成为队首决定的
假设我们现在有 Slope(q[a],q[a+1])\ge Slope(q[a+1],q[a+2])Slope(q[a],q[a+1])≥Slope(q[a+1],q[a+2]) ，那么， q[a+1]q[a+1] 点想要成为队首就只能当前面的点都弹出了，并且 Slope(q[a],q[a+1])\le f[i]Slope(q[a],q[a+1])≤f[i] ， q[a+1]q[a+1] 比 q[a]q[a] 优所以也将 q[a]q[a] 弹出时，才能成为队首。但是在这时，由于 f[i]\ge Slope(q[a],q[a+1])\ge Slope(q[a+1],q[a+2])f[i]≥Slope(q[a],q[a+1])≥Slope(q[a+1],q[a+2]) ，那么 q[a+2]q[a+2] 也应该比 q[a+1]q[a+1] 优，所以将 q[a+1]q[a+1] 弹出，意思就是，无论怎样， q[a+1]q[a+1] 都不可能做出贡献
类比一下，我们只操作队尾时，若其斜率 Slope(q[r-1],q[r])\ge Slope(q[r],i)Slope(q[r−1],q[r])≥Slope(q[r],i) ，直接弹出 q[r]q[r] 即可
那么，在我们的这个操作以后，能够保证斜率单调递增，也就是维护一个上凸包，这就是斜率优化啦！
这是一道经典的斜率优化入门题，就用这题来作个总结好了
前言：斜率优化的思想其实和高中数学的线性规划有相似之处，因此建议没学过的同学先了解一下线性规划
首先提一下单调队列优化：
当dp方程为 dp[i]=a[i]+b[j]dp[i]=a[i]+b[j] 时，这个方程是 O(n^2)O(n2) 的
这时用单调队列可以将其优化为 O(n)O(n) ，具体方法这里不再赘述
而dp方程为 dp[i]=a[i] \cdot b[j]+c[i]+d[j]dp[i]=a[i]⋅b[j]+c[i]+d[j] 时，由于存在 a[i] \cdot b[j]a[i]⋅b[j] 这个既有 ii 又有 jj 的项，以上方法就不适用了，这时就需要使用斜率优化
回到本题，设前缀和为 sum[i]sum[i] ，由题意易得dp方程：
dp[i]=min(dp[j]+(sum[i]+i-sum[j]-j-L-1)^2) (j<i)dp[i]=min(dp[j]+(sum[i]+i−sum[j]−j−L−1)2)(j<i)
但这个方程是 O(n^2)O(n2) 的，显然不满足要求，因此需要进行优化
（以下称两点斜率为 slope(A,B)slope(A,B) ）
令 a[i]=sum[i]+ia[i]=sum[i]+i ， b[i]=sum[i]+i+L+1b[i]=sum[i]+i+L+1 （这一步是为了简化计算）
则dp[i]=dp[j]+(a[i]-b[j])^2dp[i]=dp[j]+(a[i]−b[j])2
展开得
dp[i]=dp[j]+a[i]^2-2 \cdot a[i] \cdot b[j]+b[j]^2dp[i]=dp[j]+a[i]2−2⋅a[i]⋅b[j]+b[j]2
移项得
2 \cdot a[i] \cdot b[j]+dp[i]-a[i]^2=dp[j]+b[j]^22⋅a[i]⋅b[j]+dp[i]−a[i]2=dp[j]+b[j]2
将 b[j]b[j] 看作 xx ， dp[j]+b[j]^2dp[j]+b[j]2 看作 yy ，这个式子就可以看作一条斜率为 2 \cdot a[i]2⋅a[i] 的直线
而对于每个 ii 来说， a[i]a[i] 都是确定的
接下来的步骤和线性规划很相似
dp[i]dp[i] 的含义转化为：当上述直线过点 P(b[j],dp[j]+b[j]^2)P(b[j],dp[j]+b[j]2) 时，直线在 yy 轴的截距加上 a[i]^2a[i]2 （一个定值）
而题目即为找这个截距的最小值
因此，类似线性规划，我们将这条直线从下往上平移，直到过一个符合要求的点时停下，此时截距即为最小
画出图像如下（红色为目标直线）
结合图像分析可知，本题中可能为最优的 PP 点（图中用直线连接）组成了一个下凸包（其他题目可能不同，结合图像具体分析）
显然，凸包中相邻两点斜率是单调递增的
而目标直线的斜率 2 \cdot a[i]2⋅a[i] 也是单调递增的
由图像又易知，满足条件的最优 P_jPj 为第一个 slope(P_j,P_{j+1}) > 2 \cdot a[i]slope(Pj,Pj+1)>2⋅a[i] 的点
因此，我们用单调队列维护这个凸包：
设队首为 headhead ，队尾为 tailtail
-
对队首：
while(slope(P_{head},P_{head+1})<2 \cdot a[i])\quad head++while(slope(Phead,Phead+1)<2⋅a[i])head++
此时队首的点即为最优，根据它计算出 dp[i]dp[i]
-
对队尾：
while(slope(P_{tail-1},P_{tail})>slope(P_{tail-1},P_i)\quad tail--while(slope(Ptail−1,Ptail)>slope(Ptail−1,Pi)tail−−
在队尾插入 P_iPi
解释：
若 slope(P_j,P_{j+1})<2 \cdot a[i]slope(Pj,Pj+1)<2⋅a[i] ，显然 P_jPj 不是最优通过步骤1删去
因为目标直线斜率单调递增，所以当前删去的 P_jPj 一定对之后的 dp[i]dp[i] 也不是最优，不会造成影响
而操作3的理由如下：
图中红色的点为 P_iPi
显然，满足操作3的要求时， P_{tail}Ptail 在凸包内部，一定不是最优，因此可以删去
以上即为本题算法
要注意，初始化时要加入单调队列的点为 P_0P0 而不是 P_1P1 （否则就变成了第一个物品必须单独装）