最后一次修改：2024.7.16 14:39 P.M By 哈哈铭
简介
“斜率优化”顾名思义就是用斜率进行优化，让 \(DP\) 的时间复杂度更优。
一般情况下，将动态转移方程化简后得到这样的关系式：
然后通过该式进行转移，以达到优化时间复杂度的目的。
小tip：推公式前可以先试着打出暴力。
例题（模板题）
P3195 [HNOI2008] 玩具装箱
题目大意
有 \(n\) 个玩具，第 \(i\) 个玩具价值为 \(c_i\)。要求将这 \(n\) 个玩具排成一排，分成若干段。对于一段 \([l, r]\)，它的代价为 \((r − l + \sum _{i=l}^{r} c_i − L)^2\)。L 是给定常量，求分段的最小代价。
分析
首先，设 \(s_i\) 为 \(\sum _{j=1}^{i} c_j\),又可以设一个简单易懂的状态：\(f_i\) 表示前 \(i\) 个玩具分段的最小代价，然后可以的到一个暴力的方程： \(f_i=\min_{1 \leq j <i}\left\{f_j+(r-l+s_i-s_j-L)^2\right\}\)。这个是 \(O(n^2)\) 的 \(DP\)。带入另一个 \(k\),思考如何去最优解，考虑让它变形以符合斜率优化的公式。
化简过程省略……推起来太麻烦了
化简可得（当 \(1 \leq k < j \leq n\)，同时，\(j\) 比 \(k\) 更优时）：
用单调队列进行优化就OK啦~
此处斜率越大越优。
见此图：
很明显，这里的斜率是越大越好（到 \(i\) 的）。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e4+100;
ll n,L,f[N],s[N],q[N],head,tail;
inline ll mymin(ll x,ll y) {return x<y?x:y;}
inline double P(ll x) {return x*x;}
inline double X(ll x,ll y){return f[x]-f[y]+P(s[x]+x)-P(s[y]+y);}
inline double Y(ll x,ll y){return s[x]+x-s[y]-y;}
int main(){
scanf("%lld%lld",&n,&L);
for(int i=1;i<=n;i++){
scanf("%lld",&s[i]);
s[i]=s[i-1]+s[i];
}
f[0]=0;head=tail=0;
for(int i=1;i<=n;i++){
while(head<=tail&&X(q[head+1],q[head])<2*(s[i]+i-L-1)*Y(q[head+1],q[head])) head++;
f[i]=f[q[head]]+P(i-q[head]+s[i]-s[q[head]]-L-1);
while(head<=tail&&X(q[tail],q[tail-1])*Y(i,q[tail])>X(i,q[tail])*Y(q[tail],q[tail-1])) tail--;
q[++tail]=i;
}
printf("%lld",f[n]);
return 0;
}
[APIO2010] 特别行动队
题目大意
与上一题差不多，也是分若干段，但是求的是最大代价，代价的公式也不一样，肯定不一样啊，可是它仍然摆脱不了是一道斜率优化模板题的命运。
分析
这道题很简单。
首先，也是设 \(s_i\) 为 \(\sum _{j=1}^{i} c_j\)，然后得到一个 \(O(n^2)\) 的暴力 \(DP\)。
其转移方程为：
\[f_i=\max_{1 \leq j <i}\left\{f_j+a\times (s_i-s_j)^2+b\times (s_i-s_j)+c \right\} \]带入另一个 k,思考如何去最优解，考虑让它变形以符合斜率优化的公式。
化简过程省略……推起来太麻烦了 化简可得（当 \(1 \leq k < j \leq n\)，同时，\(j\) 比 \(k\) 更优时）：
用单调队列进行优化就OK啦~
此处斜率越小越优。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+100;
ll a,b,c,n,s[N],f[N],q[N],head,tail;
inline ll mymax(ll x,ll y) {return x>y?x:y;}
inline ll P(ll x) {return x*x;}
inline double slope(ll x,ll y){
return 1.0*((f[y]+a*P(s[y]))-(f[x]+a*P(s[x])))/(s[y]-s[x]);
}
int main(){
// freopen("t2.in","r",stdin);
// freopen("t2.out","w",stdout);
scanf("%lld",&n);
scanf("%lld%lld%lld",&a,&b,&c);
for(int i=1;i<=n;i++){
scanf("%lld",&s[i]);
s[i]=s[i-1]+s[i];
}
f[0]=0;
for(int i=1;i<=n;i++){
while(head<tail&&slope(q[head],q[head+1])>=2*a*s[i]+b) head++;
f[i]=f[q[head]]+a*P(s[i]-s[q[head]])+b*(s[i]-s[q[head]])+c;
while(head<tail&&slope(q[tail],i)>=slope(q[tail-1],i)) tail--;
q[++tail]=i;
}
printf("%lld",f[n]);
return 0;
}
征途
题目大意
其实与前两题差不多，只不过是要求了分的段数，公式也是光明正大地给出来了，其实同样简单，也是一道紫题。
分析
这道题同样要一个前缀和，设为 \(v_i\) 吧。
然后设出状态：\(f_{i,j}\) 表示遍历到第 \(i\) 条路，走到第 \(j\) 天。
有一个 \(O(n^3)\) 的暴力可以得出。
考虑用斜率优化，因为里面总有奇奇怪怪的计算。
然后，可以得到一个动态转移方程，很简单，就不在此列出了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e3+50;
int n,m;
ll ans,f[N][N],v[N],sum[N],l[N],hd,tl;
double getK(int c,int i,int j) {
ll x=f[i][c-1]+v[i]*v[i],xx=f[j][c-1]+v[j]*v[j];
ll y=v[i],yy=v[j];
return 1.0*(x-xx)/(y-yy);
}
int main(){
// freopen("journey.in","r",stdin);
// freopen("journey.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%lld",&v[i]);
v[i]=v[i-1]+v[i];
}
for(int i=1;i<=n;++i)
f[i][1]=v[i]*v[i];
for(int c=2;c<=m;++c){
hd=tl=1;
l[1]=c-1;
for(int i=c;i<=n;++i){
while(hd<tl&&getK(c,l[hd],l[hd+1])<2*v[i]) ++hd;
f[i][c]=f[l[hd]][c-1]+(v[l[hd]]-v[i])*(v[l[hd]]-v[i]);
while(hd<tl&&getK(c,l[tl],i)<getK(c,l[tl],l[tl-1])) --tl;
l[++tl]=i;
}
}
printf("%lld",m*f[n][m]-v[n]*v[n]);
return 0;
}
然后就差不多了。
更多能练手的题目
$ \Large\mathcal{ Thank\ \ you\ \ very\ \ much!}$
标签：return,leq,int,ll,笔记,斜率,tail,DP From： https://www.cnblogs.com/huhaoming/p/18373270