斜率优化dp
yangchenxiao · · 个人记录
之前我们学习过，对于dp方程
经做题发现，斜率优化的一般使用范围为：
那么，先看道具体例题来讲：
P3195 [HNOI2008]玩具装箱
首先，这道题的样子长得很标准：一个序列在不能改变顺序的情况下找到分块方式使得花费最小。那么，根据题意，设f[i]表示到第i个玩具最少的花费，可以列出最朴素的dp方程式为：
此时，方程式
观察方程式，满足上述形式，再观察
斜率优化是利用数形结合的思想，利用决策单调性，及时排除无用决策点而得以进行优化。
首先将原方程式的平方拆开并进行化简。为避免项太多，不妨把i、j的参数分别换元。设
\large\color{red}f[i]=f[j]+s[i]^2+(s[j]+ll)^2-2 * s[i]* s[j] - 2* s[i]* ll
斜率优化有两种常见的方式：
方法一：
大体思想为：对于一个点i，其最优决策点具有单调性。把i、j放在平面直角坐标系中会看得更清晰。
首先，将表达式化简为一个函数解析式的样子。其中，j为未知数，即y和x，i为已知数，即为k和b，那么，将只含有j的项移到左边当成y,将i、j的乘积项放在右边当做kx，将只含有i的项放在最后当做b。那么式子转化为：
\huge\color{blue}y =kx+b
这样，函数解析式就与表达式一一对应了。
此时，对于每一个i，都会有一条新的斜率为
画个图理解一下：
一条直线由下到上平移直到碰到第一个决策点。
那么最终所有决策点就形成了这样的形状
比如说这样，每一个黑点都代表一个决策点，每一条直线是以
怎样保留呢？类似于单调队列的方法，维护一个队头即为最优决策点，如果队头与队头+1的点所连线段的斜率是小于当前直线解析式的，那么，对于直线来说队头+1的点肯定更优，那么队头就没有必要保留了。
当进行插入操作时，如果队尾元素与队尾元素-1 的两点所连线段斜率大于队尾元素与i所连线段，那么队尾是没有意义的，删去即可。
最后，求解斜率时，就是
这里，因为斜率是个小数，除时容易丧失精度，所以要开long double，这样精度还是可以接受的。
方法二
这种方法是直接进行斜率的比较。
对于两个决策点
左右两边化简，约去含I的项，剩下：
\color{red}f[j_1]+(s[j_1]+ll)^2-2 * s[i]* s[j_1] <f[j_2]+(s[j_2]+ll)^2-2 * s[i]* s[j_2]
此时，继续化简，将斜率试着表示出来，原则是将只含j的放到一端，含i的放到另一端。
式子变成了：
进一步化简成：
再把含j的除过去，变成
式子左边就是
把这两个图搬过来对照式子再理解一下~
最后再附上完整的代码：
#include<bits/stdc++.h>
using namespace std;
int n,q[500005];
long long f[500005],a[500005],l,sum[500005];
long long Y(int j){
return f[j]+(sum[j]+l)*(sum[j]+l);
}
long long X(int j){
return sum[j];
}
long double slope(int i,int j){
return (long double)(Y(j)-Y(i))/(X(j)-X(i));//计算斜率，一定要用long double
}
int main(){
cin>>n>>l;
l++;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i]+1;//计算前缀和
}
int hd=1,tl=1;
q[hd]=0;
for(int i=1;i<=n;i++){
while(hd<tl&&slope(q[hd],q[hd+1])<=2*sum[i])hd++;//剔除无用队头——！！！这里需要注意：因为需要保证队列里至少留两个点形成线段，所以hd<tl，不能取等号
f[i]=f[q[hd]]+(sum[i]-sum[q[hd]]-l)*(sum[i]-sum[q[hd]]-l);//更新f[i]
while(hd<tl&&slope(q[tl-1],q[tl])>=slope(q[tl-1],i))tl--;//剔除无用队尾元素（ps：据观察，这里的大小比较一般与上面的符号是相反的）
q[++tl]=i;//入队操作
}
cout<<f[n];
return 0;
}<补>决策单调性证明
因为斜率