常见思路：
-
减少状态量：滚动数组等。
-
加速决策过程：二分、数据结构等。
-
缩小决策范围：单调队列/栈、斜率优化、四边形不等式优化等。
-
技巧性优化：前缀和等。
本文主要针对第三点展开讲解。
斜率优化
斜率优化的题目通常具有以下特征：
-
转移方程中含有乘积式，通常用平方得到。
-
有一些具有单调性的东西，如前缀和等。
尤其是第一点，是斜率优化题目极为明显的特征。
接下来，我们从一个经典题目入手，详细讲解它的原理逻辑。
P3195
很容易设计朴素 dp。
令 \(dp_i\) 表示压缩前 \(i\) 个玩具所需要的最小代价。
答案：\(dp_n\)，初始：\(dp_0=0\)。
转移：考虑对于每个 \(i\) 枚举 \(last\)，尝试将 \(last+1 \sim i\) 都放入一个容器，则 \(dp_i=dp_{last}+(i-last-1+\sum^i_{j=last} C_j-L)^2\)，其中 \(\sum\) 可以前缀和维护。
这样做的时间复杂度 \(\mathcal{O}(n^2)\)，无法接受。
注意到，\(dp_{last}\) 加上的东西是个乘积式，并且前缀和具有单调性，于是考虑斜率优化。
钦定 \(j,k\) 满足 \(k<j\)，且以 \(j\) 作为决策点比 \(k\) 更优。则有（以下令前缀和数组为 \(s_i\)）：
不妨设 \(h_{i,j}=i-j-1+s_i-s_j\)，则有：
不妨再设 \(g_i=i+s_i-1,w_j=s_j+j\)，则有：
把含有 \(g_i\) 的项放到一边，其余的放到另一边，得到：
实际上，\(g_i=w_i-1\)，于是整理得：
换元，令 \(y_i=dp_i+w_i^2,x_i=w_i\)，得：
左边这个式子长得很像直线的斜率，故称此方法为斜率优化（Convex Hull Trick）。
这个式子表明，在当前 \(i\) 的前提下，当一对 \(j,k\) 满足 \(k<j\) 且满足上式时，\(j\) 一定更优。
那么，\(i+1\) 时是否同样成立？因为前缀和单调不减，所以 \(2(w_i-L-1)\) 同样单调不减，因此 \(i+1\) 时显然成立。
于是，我们可以维护一个单调队列，每次剔除不优的队头，然后从队头转移。在插入 \(i\) 进入队列时，我希望斜率越来越大（因为不等式右边在变大），所以当队尾和次队尾的斜率比队尾和 \(i\) 的斜率小，我就弹出队尾（总不能弹出 \(i\) 吧，这样的话就不会有新的决策点进入了）。
由于每个决策点至多进队/出队一次，因此时间复杂度 \(\mathcal{O}(n)\)。
实现
#include<bits/stdc++.h>
#define int long long
using namespace std;const int N=5e5+5;
int n,m;
int dp[N],sum[N],q[N],h[N];int up(int j,int k){return (dp[j]+h[j]*h[j])-(dp[k]+h[k]*h[k]);
}
int down(int j,int k){return h[j]-h[k];
}
void sol(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>sum[i],sum[i]+=sum[i-1];int l=1,r=0;q[++r]=0;for(int i=1;i<=n;i++){h[i]=sum[i]+i;for(;l<r&&up(q[l+1],q[l])<=2*(h[i]-m-1)*down(q[l+1],q[l]);l++);dp[i]=dp[q[l]]+(sum[i]-sum[q[l]]+i-q[l]-1-m)*(sum[i]-sum[q[l]]+i-q[l]-1-m);for(;l<r&&up(i,q[r])*down(q[r],q[r-1])<=up(q[r],q[r-1])*down(i,q[r]);r--);q[++r]=i;}cout<<dp[n]<<'\n';
} signed main(){ios::sync_with_stdio(0);cin.tie(0);sol();return 0;
}
事实上，因为队列中的斜率递增，所以我们维护的决策点集合相当于一个下凸壳。如图：
（红线标出的是下凸壳，\(\texttt{x-axis}\) 为 \(w_i\)，\(\texttt{y-axis}\) 为 \(dp_i+w_i^2\)）
这也是为什么斜率优化的英文名是「Convex Hull Trick」，即所谓「凸包技巧」。