2.斜率优化动态规划
提示：由于这些式子比较长，读代码时建议点代码框右上角的“全屏”。另外，\(latex\) 比较多，可能会卡。
2.1 例题
例题2-1-1：任务安排
朴素算法：令 \(f_{i,j}\) 表示把前 \(i\) 个任务分成 \(j\) 组完成所需要花费的最小代价。
枚举第 \(j-1\) 组的最后一个任务 \(k\) ，那么转移方程就是 \(f_{i,j}=\min\limits_{0≤k<i}\Bigg({f_{k,j-1}+\bigg(S×j+\sum\limits_{p=1}\limits^i{t_p}\bigg)×\bigg(\sum\limits_{p=k+1}\limits^i{c_p}\bigg)}\Bigg)\) 。
时间复杂度 \(O(n^4)\)。
用前缀和优化，令 \(sc_i\) 表示 \(c_1\) 到 \(c_i\) 的和，令 \(st_i\) 表示 \(t_1\) 到 \(t_i\) 的和。
转移方程变为 \(f_{i,j}=\min\limits_{0≤k<i}\Big({f_{k,j-1}+(S×j+st_i)×(sc_i-sc_k)}\Big)\)。
时间复杂度 \(O(n^3)\)。
注意到每次开机所为后面的任务带来的代价是相同的。
考虑优化，令 \(f_i\) 表示完成前 \(i\) 个任务并且没有后效性的最小代价。
将每次开机所带来的代价提前计算，就可以不用考虑分了几组。
枚举上一组的最后一个任务 \(j\)，
转移方程变为 \(f_i=\min\limits_{0≤j<i}\Big({f_j+st_i×(sc_i-sc_j)+S×(sc_n-sc_j)}\Big)\)。
(这组任务自身消耗的花费+这组任务的开机对于第 \(j+1\) 到第 \(n\) 个任务额外造成的花费)
时间复杂度 \(O(n^2)\)。可以通过。
点击查看代码
int main(){
n=read();s=read();
for(ll i=1;i<=n;i++){
t[i]=t[i-1]+read();
c[i]=c[i-1]+read();
}
for(ll i=1;i<=n;i++)f[i]=0x3f3f3f3f3f3f3f3f;
for(ll i=1;i<=n;i++)
for(ll j=0;j<i;j++)f[i]=min(f[i],f[j]+t[i]*(c[i]-c[j])+s*(c[n]-c[j]));
cout<<f[n]<<'\n';
return 0;
}
例题2-1-2：任务安排
考虑继续优化。去掉 \(min\)，将式子变一下，成为 \(y=k\times x+b\) 的形式。
其中，\(y\) 是 \(f_j\) 以及只与 \(j\) 有关的项，\(k\times x\) 是所有除了 \(y\) 以外与 \(j\) 有关的项（包括与 \(j\) 有关的项和与 \(i\) 有关的项的乘积 )，其中 \(k\) 与 \(j\) 没关系，只有与 \(i\) 有关系的项和常数，\(x\) 只与 \(j\) 有关系。\(b\) 是包括 \(f_i\) 在内的所有只与 \(i\) 有关的项和常量。
说句人话：变为 \(o(j)=p(i)×q(j)+f_i+r(i)\) 其中 \(p(i)\)，\(r(i)\) 表示一些只与 \(i\) 有关的式子（可能包含常数项），\(o(j)\)，\(q(j)\) 表示一些只与 \(j\) 有关的式子（可能包含常数项，但是如果有的话可以分离在 \(r(i)\) 里，所以我们假设没有）。
在这里是变为 \(f_j=(S+st_i)×sc_j+f_i-st_i×sc_i-S×sc_n\)。
在一次转移时，\(i\) 的值是固定的，这里是为了保证 \(k\) 和 \(b\) 是常量，\(x\) 和 \(y\) 是变量，也就是说 \(p(i)\)，\(r(i)\) 都可以当作常量处理。
那么 \(x\) 和 \(y\)，也就是 \(q(j)\) 和 \(o(j)\) 就可以被表示为平面直角坐标系中的一些点。我们要求 \(f_i\) 的最小值（最大值等会再说），在 \(o(j)=p(i)×q(j)+f_i+r(i)\) 里，$
由于 \(p(i)\)，\(r(i)\) 一定，所以我们想要最小化 \(f_i\)，就是想要最小化 \(f_i+r(i)\)，也就是截距，也就是将 \(j=0\to i-1\) 的 \((q(j),o(j))\) 扔进坐标系，再用一条斜率为 \(p(i)\) 的直线从下往上移动，看最先触碰到哪个点，那就是对应的 \(j\) 。
那么哪些 \(j\) 有可能作为后面的一些 \(i\) 的答案？假设有三个点 \(a,b,c\)，\(b\) 在 \(a\)、\(c\) 中间。\(b\) 这个点没有用说明任意的斜率的直线从下往上都只能碰到 \(a\) 或 \(c\)，这当且仅当 \(b\) 在 直线 \(ac\) 上以及上方（显而易见）。
那么我们对于所有的点 \((q(j),o(j))\) 扔进坐标系后，维护一个上凸包（对于求最大值维护下凸包即可），保证两点之间连线斜率单调递增，所以可以用单调队列维护。
维护单调队列时的条件：要加入一个 \(c\)，假设队列末尾的数是 \(a\)、\(b\)，如果 \(\frac{o(c)-o(b)}{q(c)-q(b)}\le\frac{o(b)-o(a)}{q(b)-q(a)}\) 就将 \(b\) 从队尾出队。（最大值是 \(\ge\)，维护上凸包）
为了防止精度损失，可以化为 \((o(b)-o(a))×(q(c)-q(b))≥(o(c)-o(b))×(q(b)-q(a))\)。
在这里是 \((f_b-f_a)×(sc_c-sc_b)≥(f_c-f_b)×(sc_b-sc_a)\)。
在转移时，容易知道每个 \(i\) 要取的 \(j\) 满足 \(p(i)\) 介于单调队列中 \(j\) 前一个点与 \(j\) 的连线的斜率 \(k1\)，与 \(j\) 与单调队列中后一个点的连线的斜率 \(k2\) 之间。
由于 \(st_i\) 有单调性，所以 \(p(i)=S+st_i\) 有单调性，所以本题的所有最优解的 \(j\) 单调不降。
那我们就可以在维护单调队列的同时，让不符合条件（即斜率太小）的点 \(a\) 从队头出队，在这里指 \(f_b-f_a≤(st_i+S)×(sc_b-sc_a)\)。
注意，这里之所以先h++再t--是因为一开始l=r=1，默认把0塞进了队列里了。
时间复杂度：\(O(n)\)。
点击查看代码
int main(){
n=read();s=read();
for(int i=1;i<=n;i++){
t[i]=t[i-1]+read();
c[i]=c[i-1]+read();
}
for(int i=1,l=1,r=1;i<=n;i++){
while(l<r&&f[q[l+1]]-f[q[l]]<=(c[q[l+1]]-c[q[l]])*(s+t[i]))l++;
f[i]=f[q[l]]+t[i]*(c[i]-c[q[l]])+s*(c[n]-c[q[l]]);
while(l<r&&(f[q[r]]-f[q[r-1]])*(c[i]-c[q[r]])>=(f[i]-f[q[r]])*(c[q[r]]-c[q[r-1]]))r--;
q[++r]=i;
}
cout<<f[n]<<'\n';
return 0;
}
例题2-1-3：[SDOI2012]任务安排
这里与 \(1-2\) 唯一的不同就是 \(t_i\) 可能为负。那就说明 \(st_i\) 不单增，所以不再能出队。所以要维护完整的下凸包。
由于下凸包的斜率是单增的，所以可以查询时考虑二分。
时间复杂度：\(O(nlogn)\)。
点击查看代码
ll bs(ll l,ll r,ll x){
ll res=0;
while(l<=r){
ll mid=(l+r)/2;
if(f[q[mid+1]]-f[q[mid]]>(c[q[mid+1]]-c[q[mid]])*x)res=mid,r=mid-1;
else l=mid+1;
}
return q[res];
}
int main(){
n=read();s=read();
for(ll i=1;i<=n;i++){
t[i]=t[i-1]+read();
c[i]=c[i-1]+read();
}
for(ll i=1,l=1,r=1;i<=n;i++){
ll j=bs(l,r,s+t[i]);
f[i]=f[j]+t[i]*(c[i]-c[j])+s*(c[n]-c[j]);
while(l<r&&(f[q[r]]-f[q[r-1]])*(c[i]-c[q[r]])>=(f[i]-f[q[r]])*(c[q[r]]-c[q[r-1]]))r--;
q[++r]=i;
}
cout<<f[n]<<'\n';
return 0;
}
例题2-2：[NOIP2018 普及组] 摆渡车
令 \(f_i\) 表示第 \(i\) 时刻摆渡车从人大附中出发，此时所有 \(t\) 小于等于 \(i\) 的正在等待的人都上车，所有 \(t\) 小于等于 \(i\) 的人的总等待时间的最小值。
枚举上一次出发的时间 \(j\)，这一题可以列出 \(f_i=\min\limits_{0≤j≤i-m}\bigg({f_j+\sum\limits_{t_k=j+1}\limits^{t_k=i}(i-t_k)}\bigg)\) 的转移方程。
用前缀和优化一下，令 \(p_i\) 等于所有 \(t_k\) 小于等于 \(i\) 的人的个数，令 \(s_i\) 等于所有 \(t_k\) 小于等于 \(i\) 的人的 \(t_k\) 的和。
那么转移方程就可以变为 \(f_i=\min\limits_{0≤j≤i-m}(f_j+i×(p_i-p_j)-s_i+s_j)\)。
去掉 \(min\)，移项，将只与 \(j\) 有关的放在左边，将与 \(i\) 和 \(j\) 有关的放在中间，将 \(f_i\) 和其它与 \(i\) 有关的放在右边，
得到 \(f_j+s_j=i×p_j+f_i+s_i-i×p_i\)。
\(y=k×x+b\)
那么我们就可以将 \((x,y)\) ，即 \((p_j,f_j+s_j)\) 扔进坐标系。注意到 \(i\) 单增，所以在队尾维护下凸包，在队头去掉斜率小于等于 \(i\) 的线段就可以了。
注意要 \(f_i=p_i\times i-s_i\) 是因为这一题不像上一题一样一定从 \(0\) 开始被初始化，所以要考虑从任意 \(i∈[0,mx]\) 开始的情况。
点击查看代码
ll y(ll w){return f[w]+s[w];}
int main(){
n=read();m=read();
for(ll i=1,x;i<=n;i++){x=read();p[x]++;s[x]+=x;mx=max(mx,x);}
for(ll i=1;i<mx+m;i++){p[i]+=p[i-1];s[i]+=s[i-1];}
for(ll i=0,l=1,r=0;i<mx+m;i++){
if(i>=m){
while(l<r&&(y(i-m)-y(q[r]))*(p[q[r]]-p[q[r-1]])<=(y(q[r])-y(q[r-1]))*(p[i-m]-p[q[r]]))r--;
q[++r]=i-m;
}
while(l<r&&y(q[l+1])-y(q[l])<=i*(p[q[l+1]]-p[q[l]]))l++;
f[i]=p[i]*i-s[i];
if(l<=r)f[i]=min(f[i],f[q[l]]+i*(p[i]-p[q[l]])-s[i]+s[q[l]]);
}
for(ll i=0;i<m;i++)ans=min(ans,f[i+mx]);
cout<<ans<<'\n';
return 0;
}
例题2-3：[HNOI2008]玩具装箱
什么水题，一发过。令 \(f_i\) 表示前 \(i\) 个玩具放在若干箱子里的最小费用。
容易列出转移方程：\(f_i=\min\limits_{0≤j<i}\Bigg(f_j+\bigg(i-j-1-L+\sum\limits_{k=j+1}\limits^i{c_k}\bigg)^2\Bigg)\)。
那我们令 \(s_i=i+\sum\limits_{k=1}\limits^i{c_k}\)，\(L=L+1\)，转移方程变为 \(f_i=\min\limits_{0≤j<i}(f_j+(s_i-s_j-L)^2)\)，拆开变成 \(f_i=\min\limits_{0≤j<i}(f_j+s_i^2+s_j^2+L^2-2s_i\times s_j-2s_i\times L+2s_j\times L)\)。
去掉 \(min\)，移项，得到 \(f_j+s_j^2+2s_j\times L=2s_i×s_j+f_i-s_i^2+2s_i\times L-L^2\)。
\(y=k\times x+b\)
那么我们将 \((s_j,f_j+s_j^2+2s_j\times L)\) 扔进坐标系，注意到 \(2s_i\) 单增，在队头把斜率小于等于 \(2s_i\) 的出队，在队尾维护下凸包即可。
点击查看代码
ll y(ll w){return f[w]+s[w]*s[w]+2*s[w]*L;}
int main(){
n=read();L=read()+1;
for(ll i=1;i<=n;i++)s[i]=s[i-1]+read()+1;
for(ll i=1,l=1,r=1;i<=n;i++){
while(l<r&&y(q[l+1])-y(q[l])<=2*s[i]*(s[q[l+1]]-s[q[l]]))l++;
f[i]=f[q[l]]+(s[i]-s[q[l]]-L)*(s[i]-s[q[l]]-L);
while(l<r&&(y(i)-y(q[r]))*(s[q[r]]-s[q[r-1]])<=(y(q[r])-y(q[r-1]))*(s[i]-s[q[r]]))r--;
q[++r]=i;
}
cout<<f[n]<<'\n';
return 0;
}
习题
习题2-1：丝之歌
点击查看代码
bool cmp(pair<ll,ll>qwq,pair<ll,ll>qaq){
return qwq.first==qaq.first?qwq.second>qaq.second:qwq.first<qaq.first;
}
ll x(ll w){return a[g[w+1]-1];}
int main(){
n=read();m=read();
for(ll i=1;i<=n;i++)a[i]=read();
for(ll i=1;i<=n;i++)b[i]=read();
a[0]=b[n+1]=1e9;g[0]=1;
for(ll i=1;i<=n;i++)a[i]=min(a[i],a[i-1]);
for(ll i=n;i>=1;i--)b[i]=min(b[i],b[i+1]);
for(ll i=1;i<=m;i++)c[i].first=read(),c[i].second=read();
sort(c+1,c+m+1,cmp);
for(ll i=1,mx=0;i<=m;i++)
if(c[i].second>mx){
g[++t]=c[i].first;
mx=h[t]=c[i].second;
}
for(ll i=1,l=1,r=1;i<=t;i++){
while(l<r&&f[q[l+1]]-f[q[l]]<=b[h[i]+1]*(x(q[l])-x(q[l+1])))l++;
f[i]=f[q[l]]+x(q[l])*b[h[i]+1];
while(l<r&&(f[i]-f[q[r]])*(x(q[r])-x(q[r-1]))>=(f[q[r]]-f[q[r-1]])*(x(i)-x(q[r])))r--;
q[++r]=i;
}
cout<<f[t]<<'\n';
return 0;
}
习题2-2：[ZJOI2007] 仓库建设
点击查看代码
ll y(ll w){return f[w]+t[w];}
int main(){
n=read();
for(ll i=1;i<=n;i++){
x[i]=read();p[i]=read();c[i]=read();
s[i]=s[i-1]+p[i];t[i]=t[i-1]+x[i]*p[i];
}
for(ll i=1,l=1,r=1;i<=n;i++){
while(l<r&&y(q[l+1])-y(q[l])<=x[i]*(s[q[l+1]]-s[q[l]]))l++;
f[i]=f[q[l]]+c[i]+x[i]*(s[i]-s[q[l]])-t[i]+t[q[l]];
while(l<r&&(y(q[r])-y(q[r-1]))*(s[i]-s[q[r]])>=(y(i)-y(q[r]))*(s[q[r]]-s[q[r-1]]))r--;
q[++r]=i;
}
for(ll i=n;i>=1;i--){
ans=min(ans,f[i]);
if(p[i])break;
}
cout<<ans<<'\n';
return 0;
}
习题2-3：CF311B Cats Transport
有时候要记得初始化，尤其是取最小值时。
点击查看代码
ll y(ll v,ll w){return f[v-1][w]+s[w];}
int main(){
n=read();m=read();p=read();
for(ll i=2;i<=n;i++)d[i]=d[i-1]+read();
for(ll i=1,h,t;i<=m;i++){h=read();t=read();a[i]=t-d[h];}
sort(a+1,a+m+1);
for(ll i=1;i<=m;i++)s[i]=s[i-1]+a[i];
memset(f,63,sizeof(f));f[0][0]=0;
for(ll i=1,j,l,r;i<=p;i++)
for(q[j=l=r=1]=0;j<=m;j++){
while(l<r&&y(i,q[l+1])-y(i,q[l])<=a[j]*(q[l+1]-q[l]))l++;
f[i][j]=f[i-1][q[l]]+a[j]*(j-q[l])+s[q[l]]-s[j];
while(l<r&&(y(i,q[r])-y(i,q[r-1]))*(j-q[r])>=(y(i,j)-y(i,q[r]))*(q[r]-q[r-1]))r--;
q[++r]=j;
}
cout<<f[p][m]<<'\n';
return 0;
}
习题2-4：[APIO2014] 序列分割
这题细节超多，还卡时间卡空间。这题算出来是把 \((s_k,f_k-s_k^2)\) 扔进队，求的是最大值，所以维护上凸包。查询时是查询一个非正的斜率：\(-s_j\)，所以要记得看不等号的方向。
点击查看代码
ll y(ll v,ll w){return f[v][w]-s[w]*s[w];}
int main(){
n=read();m=read();
for(ll i=1;i<=n;i++)s[i]=s[i-1]+read();
for(ll i=1,j,l,r,p=0,c=1;i<=m;i++,p^=1,c^=1)
for(q[j=l=r=1]=0;j<=n;j++){
while(l<r&&y(p,q[l+1])-y(p,q[l])>=-s[j]*(s[q[l+1]]-s[q[l]]))l++;
f[c][j]=f[p][q[l]]+s[q[l]]*(s[j]-s[q[l]]);g[i][j]=q[l];
while(l<r&&(y(p,q[r])-y(p,q[r-1]))*(s[j]-s[q[r]])<=(y(p,j)-y(p,q[r]))*(s[q[r]]-s[q[r-1]]))r--;
q[++r]=j;
}
cout<<f[m&1][n]<<'\n';
for(ll i=m,x=n;i>=1;i--)printf("%lld ",x=g[i][x],"\n"[i==1]);
return 0;
}
习题2-5：[APIO2010] 特别行动队
点击查看代码
ll y(ll w){return f[w]+a*s[w]*s[w]-b*s[w];}
int main(){
n=read();a=read();b=read();c=read();
for(ll i=1;i<=n;i++)s[i]=s[i-1]+read();
for(ll i=1,l=1,r=1;i<=n;i++){
while(l<r&&y(q[l+1])-y(q[l])>=2ll*a*s[i]*(s[q[l+1]]-s[q[l]]))l++;
f[i]=f[q[l]]+a*(s[i]-s[q[l]])*(s[i]-s[q[l]])+b*(s[i]-s[q[l]])+c;
while(l<r&&(y(i)-y(q[r]))*(s[q[r]]-s[q[r-1]])>=(y(q[r])-y(q[r-1]))*(s[i]-s[q[r]]))r--;
q[++r]=i;
}
cout<<f[n]<<'\n';
return 0;
}
习题2-6：[USACO08MAR]Land Acquisition G
点击查看代码
inline bool cmp(_ s,_ t){return s.x==t.x?s.y>t.y:s.x>t.x;};
int main(){
n=read();
for(ll i=1;i<=n;i++)a[i]=_{read(),read()};
sort(a+1,a+n+1,cmp);
for(ll i=1;i<=n;i++)
if(a[i].y>a[m].y)a[++m]=a[i];
for(ll i=1,l=1,r=1;i<=m;i++){
while(l<r&&f[q[l+1]]-f[q[l]]<=-a[i].y*(a[q[l+1]+1].x-a[q[l]+1].x))l++;
f[i]=f[q[l]]+a[i].y*a[q[l]+1].x;
while(l<r&&(f[i]-f[q[r]])*(a[q[r]+1].x-a[q[r-1]+1].x)>=(f[q[r]]-f[q[r-1]])*(a[i+1].x-a[q[r]+1].x))r--;
q[++r]=i;
}
cout<<f[m]<<'\n';
return 0;
}
习题2-7：[SDOI2016]征途
点击查看代码
ll y(ll v,ll w){return f[v-1][w]+s[w]*s[w];}
int main(){
n=read();m=read();
for(ll i=1;i<=n;i++)s[i]=s[i-1]+read();
memset(f,63,sizeof(f));f[0][0]=0;
for(ll i=1,j,l,r;i<=m;i++)
for(q[j=l=r=1]=0;j<=n;j++){
while(l<r&&y(i,q[l+1])-y(i,q[l])<=2*s[j]*(s[q[l+1]]-s[q[l]]))l++;
f[i][j]=f[i-1][q[l]]+(s[j]-s[q[l]])*(s[j]-s[q[l]]);
while(l<r&&(y(i,q[r])-y(i,q[r-1]))*(s[j]-s[q[r]])>=(y(i,j)-y(i,q[r]))*(s[q[r]]-s[q[r-1]]))r--;
q[++r]=j;
}
cout<<m*f[m][n]-s[n]*s[n]<<'\n';
return 0;
}
习题2-8：[JSOI2009] 火星藏宝图
这一题很容易列出方程，先按照 \(x\)、\(y\) 从小到大排好序，令 \(f_i\) 是从第 \(1\) 个点到第 \(i\) 个点的最大收益，那么 \(f_i=\max\limits_{1≤j<i∩y_j≤y_i}(f_j-(x_i-x_j)^2-(y_i-y_j)^2+v_i)\)。时间复杂度 \(O(n^2)\)。
可以注意到一个性质：如果 \(i\) 之前同一列有若干点，那么选该列行数最大的点转移来最优，因为 \(a^2+b^2<(a+b)^2\)。那么可以记录第 \(j\) 列行数最大的格子为 \(p_j\)。时间复杂度 \(O(nm)\)。
拆开得到 \(f_i=f_j-x_i^2-x_j^2-y_i^2-y_j^2+2x_i\times x_j+2y_i\times y_j+v_i\)，发现 \(i\) 和 \(j\) 的乘积项有不同的两项，无法进行斜率优化。
考虑改变转移式，令 \(f_{i,j}\) 表示游览到 \((i,j)\) 时的最大收益，枚举转移来的列 \(k\)，得到 \(f_{i,j}=\max\limits_{1≤k≤j}(f_{p_k,k}-(i-p_k)^2-(j-k)^2+v_{i,j})\)。时间复杂度 \(O(m^3)\)。
注意到这里 \(i\) 是定值。拆开得到 \(f_{p_k,k}+2i×p_k-k^2-p_k^2=-2j×k+f_{i,j}+i^2+j^2-v_{i,j}\)。
那么我们就可以把 \((x,y)=(k,f_{p_k,k}+2i×p_k-k^2-p_k^2)\) 扔进队列。由于求最大值，所以维护上凸包，队头把斜率大于等于 \(-2j\) 的出队即可。时间复杂度 \(O(m^2)\)。
点击查看代码
ll y(ll qwq,ll k){return f[p[k]][k]+2*qwq*p[k]-k*k-p[k]*p[k];}
int main(){
n=read();m=read();
while(n--){
ll x=read(),y=read(),z=read();
v[x][y]=z;
}
p[1]=1;memset(f,200,sizeof(f));f[1][1]=v[1][1];v[1][1]=0;
for(ll i=1,j,l,r;i<=m;i++)
for(j=l=1,r=0;j<=m;j++){
if(p[j]){
while(l<r&&(y(i,q[r])-y(i,q[r-1]))*(j-q[r])<=(y(i,j)-y(i,q[r]))*(q[r]-q[r-1]))r--;
q[++r]=j;
}
if(v[i][j]){
while(l<r&&y(i,q[l+1])-y(i,q[l])>=-2*j*(q[l+1]-q[l]))l++;
f[i][j]=f[p[q[l]]][q[l]]+v[i][j]-(i-p[q[l]])*(i-p[q[l]])-(j-q[l])*(j-q[l]);p[j]=i;
while(l<r&&(y(i,q[r])-y(i,q[r-1]))*(j-q[r])<=(y(i,j)-y(i,q[r]))*(q[r]-q[r-1]))r--;
q[++r]=j;
}
}
cout<<f[m][m]<<'\n';
return 0;
}
习题2-9：[蓝桥杯 2015 国 B] 居民集会
这一提要注意算斜率乘的时候爆 long long ，要开 __int128 。
点击查看代码
ll y(ll v,ll w){return f[v-1][w]+a[w];}
int main(){
n=read();m=read();
for(ll i=1,o;i<=n;i++){d[i]=read();o=read();a[i]=a[i-1]+d[i]*o;b[i]=b[i-1]+o;}
for(ll i=1;i<=n;i++)f[1][i]=d[i]*b[i]-a[i];
for(ll i=2,j,l,r;i<=3;i++)
for(j=l=r=1;j<=n;j++){
while(l<r&&y(i,q[l+1])-y(i,q[l])<=d[j]*(b[q[l+1]]-b[q[l]]))l++;
f[i][j]=f[i-1][q[l]]+d[j]*(b[j]-b[q[l]])-a[j]+a[q[l]];
while(l<r&&(y(i,j)-y(i,q[r]))*(b[q[r]]-b[q[r-1]])<=(y(i,q[r])-y(i,q[r-1]))*(b[j]-b[q[r]]))r--;
q[++r]=j;
}
for(ll i=1;i<=n;i++)ans=min(ans,f[3][i]+m*(b[n]-b[i])-a[n]+a[i]);
write(ans);
return 0;
}
习题2-10：大胃王
这一题不仅要求最小值，还要求非严格次小值，那么就要维护 \(3\) 个下凸包，总之就是一堆细节。
式子（令最小值为 \(f_i\)，次小值为 \(g_i\)，\((second)min\) 指次小值）：\(f_i=\min\limits_{0≤j<i}(f_j+(s_i-s_j-L)^2)\)，\(g_i=\min(\min\limits_{2≤j<i}{g_j+(s_i-s_j-L)^2},(second)\min\limits_{0≤j<i}(f_j+(s_i-s_j-L)^2)\)。
那么对于前两个式子直接斜率优化就行，就是模板，这里给出式子：\(f_j+s_j^2+2L\times s_j=2s_i×s_j+f_i-s_i^2-L^2+2s_i\times L\)。(\(g\) 同理）
对于第 \(3\) 个式子，考虑开一个新的队列 \(o\) 维护凸包，记录从 \(f\) 对应的队列 \(q\) 里从队尾退出来的点，将 \(x\) 值大于 \(q_{r+1}\) 的全部从 \(o\) 中退出，因为这些点无法再作为次小值了。然后将 \(q\) 退出来的东西一个个入队 \(o\)，维护下凸包就可以了。
查询时直接将 \(o\)、\(p\)、\(q\) 中斜率小于等于 \(2s_i\) 的点弹出就可以了。注意在转移 \(g\) 时要特判一些细节，比如说 \(o\) 为空，或者次小值仍在 \(q\) 里（那么此时次小值只可能为 \(q_{l-1}\) 或 \(q_{l+1}\)）。
吐槽：题解区就一篇出题人的题解，复杂度 O(nlogn) ，提交记录里有一半是 O(nlogn) 的，然后我一个 O(n) 的喜提最劣解。调了一早上。
点击查看代码
inline ll yf(ll w){return f[w]+s[w]*s[w]+2*m*s[w];}
inline ll yg(ll w){return g[w]+s[w]*s[w]+2*m*s[w];}
inline ll cal(ll w,ll v){return (s[w]-s[v]-m)*(s[w]-s[v]-m);}
int main(){
n=read();m=read();g[0]=g[1]=1e12;
for(ll i=1;i<=n;i++)s[i]=s[i-1]+read();
for(ll i=1,l=1,r=1,h=1,t=0,a=1,b=0,pos;i<=n;i++){
while(a<b&&yf(o[a+1])-yf(o[a])<=2*s[i]*(s[o[a+1]]-s[o[a]]))a++;
while(l<r&&yf(q[l+1])-yf(q[l])<=2*s[i]*(s[q[l+1]]-s[q[l]]))l++;
while(h<t&&yg(p[h+1])-yg(p[h])<=2*s[i]*(s[p[h+1]]-s[p[h]]))h++;
f[i]=f[q[l]]+cal(i,q[l]);pos=r;
if(i>1)g[i]=g[p[h]]+cal(i,p[h]);
if(i>1&&l<r)g[i]=min(g[i],f[q[l+1]]+cal(i,q[l+1]));
if(i>1&&l>1)g[i]=min(g[i],f[q[l-1]]+cal(i,q[l-1]));
if(i>1&&a<=b)g[i]=min(g[i],f[o[a]]+cal(i,o[a]));
if(i>1&&a>b&&a>1)g[i]=min(g[i],f[o[a-1]]+cal(i,o[a-1]));
while(l<r&&(yf(i)-yf(q[r]))*(s[q[r]]-s[q[r-1]])<=(yf(q[r])-yf(q[r-1]))*(s[i]-s[q[r]]))r--;
if(r!=pos){
while(a<b&&o[b]>q[r+1])b--;
for(ll j=r+1;j<=pos;j++){
while(a<b&&(yf(q[j])-yf(o[b]))*(s[o[b]]-s[o[b-1]])<=(yf(o[b])-yf(o[b-1]))*(s[q[j]]-s[o[b]]))b--;
o[++b]=q[j];
}
}
while(h<t&&(yg(i)-yg(p[t]))*(s[p[t]]-s[p[t-1]])<=(yg(p[t])-yg(p[t-1]))*(s[i]-s[p[t]]))t--;
q[++r]=p[++t]=i;
}
write(f[1]);putchar('\n');
for(ll i=2;i<=n;i++){write(f[i]);putchar(' ');write(g[i]);putchar('\n');}
return 0;
}
习题2-11：P3994 高速公路（疑似错题）
这题是错题，但是题面改一改，加上“小 T 只能往根节点方向坐车”就对了，正解做法十分的巧妙，我希望不要取缔这一题。
首先加上只能往根节点方向坐车的条件（否则这一题也许没有 \(O(n^2)\) 以下的作法），令 \(f_i\) 表示从 \(i\) 坐车到根节点的最小花费，那么 \(f_i=\min\limits_{j∈anc(i)}(f_j+(s_i-s_j)*p_i+q_i)\) 。拆开移项得到 \(f_j=p_i×s_j+f_i-s_i\times p_i-q_i\) 。那么维护一个下凸包就可以了。但是一个点可能在 DFS 时多次入队、出队，所以可能会被卡成 O(不知道什么东西)，所以稳妥起见用一个二分，二分队列开头，使它的斜率够大；二分队列结尾维护凸包，这样只要每次在单调栈里修改一个点就行，最后再回溯，时间复杂度 \(O(nlogn)\)，最后再回溯。
要注意队列为空的情况，处理细节。
点击查看代码
void dfs(ll x,ll l,ll r){
ll c=l,d=r-1,g=r,h=r+1,qwq;
while(c<=d){
ll mid=(c+d)/2;
if(f[q[mid+1]]-f[q[mid]]>a[x]*(s[q[mid+1]]-s[q[mid]]))g=mid,d=mid-1;
else c=mid+1;
}
f[x]=f[q[g]]+(s[x]-s[q[g]])*a[x]+b[x];c=l+1,d=r;
while(c<=d){
ll mid=(c+d)/2;
if((f[q[mid]]-f[q[mid-1]])*(s[x]-s[q[mid]])>(f[x]-f[q[mid]])*(s[q[mid]]-s[q[mid-1]]))h=mid,d=mid-1;
else c=mid+1;
}
qwq=q[h];q[h]=x;
for(ll i=0;i<v[x].size();i++)s[v[x][i]]+=s[x],dfs(v[x][i],g,h);
q[h]=qwq;
}
int main(){
n=read();q[1]=1;
for(ll i=2;i<=n;i++){v[read()].push_back(i);s[i]=read();a[i]=read();b[i]=read();}
for(ll i=0;i<v[1].size();i++)dfs(v[1][i],1,1);
for(ll i=2;i<=n;i++){write(f[i]);putchar('\n');}
return 0;
}
习题2-12：P6302 [NOI2019] 回家路线
我觉得可以再加强，让 \(m,n,max{q}≤10^6\)。题解
总结：斜率优化适用于 \(o(j)=p(i)×q(j)+f_i+r(i)\) 的动态规划，其中 \(o(j),q(j)\) 表示只与 \(j\) 和常数有关的项，\(p(i),r(i)\) 表示只与 \(i\) 和常数有关的项，而且 \(q(j)\) 单调不降。如果 \(p(i)\) 也单调，就可以直接退队，否则要在单调栈上二分。