- 斜率优化，一般是在转移方程中当前为 \(i\)，枚举决策点 \(j\)，然后化简式子出现同时与 \(i\) 和 \(j\) 有关的项（如果没有可以单调队列）。这样的话有点像一次函数，形如 \(y=kx+b\)，那么这里的 \(kx\) 就是与\(i\) 和 \(j\) 有关的项（具体题目具体分析）。问题变成查询最有决策点。
- 如果式子中的 \(x\) 与 \(y\) 都有单调性，可以使用单调队列线性维护。否则有两种做法：维护凸壳并二分或李超树（也可以平衡树或 cdq 分治，但我不会，就不弄巧成拙了）。这些做法是带一个 log 的。
经典套路：
\(1.\) 写出朴素转移方程。
\(2.\) 化简并设出 \(x,y,k,b\)，根据所求决定维护上凸还是下凸（最大值还是最小值）。
\(3.\) 看单调性决定维护方式。
例题1 P3195 [HNOI2008] 玩具装箱
【题意】
给定一个序列，要求将其划分成若干段，一段划分为 \([i,j]\) 的费用为 \((j-i+\sum_{k=i}^jC_k-L)^2\)（这里的 \(C_k\) 为给定数组，\(L\) 为给定常量）。最小化划分序列的费用和。
【解析】
朴素的转移方程为：（设 \(f_i\) 表示考虑到 \(i\) 的答案，\(s_i\) 表示 \(C_i\) 的前缀和）
\[ f_i=\min_{1\le j<i}(f_j+[i-(j+1)+s_i-s_j-L]^2) \]换元并化简，设 \(a_i=s_i+i，b_i=s_i+i+L+1\)。
\[ \begin{aligned} &f_i=\min_{1\le j<i}(f_j+[a_i-b_j]^2)\\ &f_i=\min_{1\le j<i}(f_j+a_i^2+b_j^2-2\times a_i\times b_j)\\ \end{aligned} \]先不管取 \(\min\)，先推式子，并把只与 \(j\) 有关的移到一边，尝试分离 \(i\) 和 \(j\)。
\[ \begin{aligned} f_i&=f_j+a_i^2+b_j^2-2\times a_i\times b_j\\ f_j+b_j^2&=f_i-a_i^2+2\times a_i\times b_j \end{aligned} \]我们发现，如果设 \(y=f_j+b_j^2，k=2\times a_i，x=b_j，b=f_i-a_i^2\)，那么方程变成了一个一次函数形式 \(y=kx+b\)。所以要做的就是在二维平面中找一个斜率固定的直线使 \(b\) 最小。
观察数据，\(y=f_j+b_j^2\) 和 \(x=b_j\) 都单调递增，所以使用单调队列优化，时空复杂度线性。
放个单调队列斜优的板子吧。
#include<iostream>
using namespace std;
#define int long long
#define endl '\n'
#define N 100005
int n,l;
int s[N],f[N],q[N];
int up(int i,int j){
return (f[j]+s[j]*s[j]+2*l*s[j])-(f[i]+s[i]*s[i]+2*l*s[i]);
}
int down(int i,int j){
return s[j]-s[i];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>l;
l=l+1;
for(int i=1,x;i<=n;++i) cin>>x,s[i]=s[i-1]+x;
for(int i=1;i<=n;++i) s[i]=s[i]+i;
int h=1,t=1;
q[1]=0;
for(int i=1;i<=n;++i){
int k=2*s[i];
while(h<t&&up(q[h],q[h+1])<=down(q[h],q[h+1])*k) h++;
int j=q[h];
f[i]=f[j]+(s[i]-s[j]-l)*(s[i]-s[j]-l);
while(h<t&&up(q[t-1],q[t])*down(q[t],i)>=up(q[t],i)*down(q[t-1],q[t])) t--;
q[++t]=i;
}
cout<<f[n]<<endl;
return 0;
}
与此题类似的题：
例题2 P4072 [SDOI2016] 征途
【题意】
给定长度为 \(n\) 的序列，将其划分为 \(m\) 段，使得这 \(m\) 段各自求和后的总方差最小，输出方差 \(\times m^2\)。
形式化地，设 \(b_i=\sum_{j=l_i}^{r_i}a_j\)，\(v=\frac{\sum_{i=1}^m(b_i-\bar{b})^2}{m}\)，求最小的 \(v\times m^2\)。其中 \(\forall i\in [1,m-1]\)，\(l_{i+1}=r_i+1\)。
【解析】
推推柿子。
\[ \begin{aligned} v&=\frac{\sum_{i=1}^m(b_i-\bar{b})^2}{m}\\ &=\frac{(b_1-\bar{b})^2+ (b_2-\bar{b})^2+...+ (b_m-\bar{b})^2}{m}\\ &=\frac{m\times(\bar{b})^2+\sum_{i=1}^mb_i^2-2\times \bar{b}\times\sum_{i=1}^mb_i}{m}\\ &=\frac{m\times(\frac{\sum_{i=1}^mb_i}{m})^2+\sum_{i=1}^mb_i^2-2\times \frac{\sum_{i=1}^mb_i}{m}\times\sum_{i=1}^mb_i}{m}\\ &=\frac{\frac{(\sum_{i=1}^mb_i)}{m}^2+\sum_{i=1}^mb_i^2-2\times \frac{(\sum_{i=1}^mb_i)^2}{m}}{m}\\ &=\frac{\sum_{i=1}^mb_i^2- \frac{(\sum_{i=1}^mb_i)^2}{m}}{m}\\ v\times m^2&=m\times\sum_{i=1}^mb_i^2-(\sum_{i=1}^mb_i)^2 \end{aligned} \]可以发现， \(-(\sum_{i=1}^mb_i)^2\) 无论怎么划分都不会变，都是 \(-(\sum_{i=1}^na_i)^2\)，所以就变成最小化 \(m\times\sum_{i=1}^mb_i^2\)。
考虑 DP 设 \(f_{i,j}\) 表示走到 \(a_i\)，是第 \(j\) 天的最小 \(\sum_{}\)（最后再乘 \(m\)）。那么朴素式子很好推（这里的 \(s_i\) 表示 \(a_i\) 的前缀和）：
\[f_{i,j}=\min_{1\le k<i}(f_{k,j-1}+(s_i-s_k)^2) \]直接做是 \(O(n^3)\) 的，发现这是斜率优化的经典形式，即
\[\begin{aligned} f_{i,j}&=\min_{1\le k<i}(f_{k,j-1}+s_i^2+s_k^2-2\times s_i\times s_k)\\ f_{i,j}&=f_{k,j-1}+s_i^2+s_k^2-2\times s_i\times s_k\\ f_{k,j-1}+s_k^2&=f_{i,j}-s_i^2+2\times s_i\times s_k \end{aligned} \]设 \(y=f_{k,j-1}+s_k^2,k=2\times s_i,x=s_k,b=f_{i,j}-s_i^2\)，变成一次函数形式，即可斜率优化。此题斜率优化是二维的，使用了单调队列。
放个二维斜率优化的板子。使用了辅助数组 \(g\)，优化成线性空间。
#include<iostream>
using namespace std;
#define int long long
#define N 3005
int n,m;
int s[N],q[N],f[N],g[N];
int up(int i,int j){
return (g[j]+s[j]*s[j])-(g[i]+s[i]*s[i]);
}
int down(int i,int j){
return s[j]-s[i];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=1,x;i<=n;++i) cin>>x,s[i]=s[i-1]+x,g[i]=s[i]*s[i];
for(int j=2;j<=m;++j){
int h=1,t=1;
q[1]=j-1;
for(int i=j;i<=n;++i){
while(h<t&&up(q[h],q[h+1])<=down(q[h],q[h+1])*2*s[i]) h++;
int p=q[h];
f[i]=g[p]+(s[i]-s[p])*(s[i]-s[p]);
while(h<t&&up(q[t-1],q[t])*down(q[t],i)>=up(q[t],i)*down(q[t-1],q[t])) t--;
q[++t]=i;
}
for(int i=1;i<=n;++i) g[i]=f[i];
}
cout<<m*f[n]-s[n]*s[n]<<endl;
return 0;
}
与此题相似的题：
标签：frac,mb,int,sum,times,斜率,bar,优化 From： https://www.cnblogs.com/Mr-KaYa/p/18094099