前言

斜率优化是一种经典的单调队列优化类型，虽然它的名字很高大上，但是其思想内核非常简单，这篇博客就是用来帮助各位快速入门的

提示：本博客以单调队列的思想理解斜率优化

引入

dp 优化可以怎么分类？

  1. 数据结构维护决策点集的插入与查找

  2. 算法维护决策点集大小，取出无用决策点

而斜率优化 dp 属于第二者，且常常用于优化序列分割问题

Q1

P3195

A1

先列出一个朴素的 dp 方程:

\(dp_i = min(dp_j+(pre[i]+i-pre[j]-j-L-1)^2)\)

然后我们考虑决策点 \(j,k\) 满足 \(k<j\) 且 \(j\) 优于 \(k\)

那么有：

\(dp_j + (pre[i]+i-L-1)^2 + (pre[j]+j)^2 – 2 \times (pre[i]+i-L-1) \times (pre[j]+j) < dp_k + (pre[i]+i-L-1)^2 + (pre[k]+k)^2 – 2 \times (pre[i]+i-L-1) \times (pre[k]+k)\)

\(dp_j + (pre[j]+j)^2 – 2 \times (pre[i]+i-L-1) \times (pre[j]+j) < dp_k + (pre[k]+k)^2 – 2 \times (pre[i]+i-L-1) \times (pre[k]+k)\)

\(dp_j + (pre[j]+j)^2 – dp_k + (pre[k]+k)^2 < 2 \times (pre[i]+i-L-1) \times (pre[j]+j) – 2 \times (pre[i]+i-L-1) \times (pre[k]+k)\)

\(2 \times (pre[i]+i-L-1) \times((pre[j]+j) -(pre[k]+k)) > dp_j + (pre[j]+j)^2 – dp_k + (pre[k]+k)^2\)

然后我们发现这个等式两边全部具有单调性，所以就可以用单调队列维护最优答案

#include#define int long longusing namespace std;const int maxn = 1e6+114;int sum[maxn],q[maxn];int dp[maxn];int n,L;int top(int j,int k){return (sum[j]+j)*(sum[j]+j)+dp[j]-(sum[k]+k)*(sum[k]+k)-dp[k];}int down(int j,int k){return sum[j]+j-sum[k]-k;} signed main(){cin>>n>>L;for(int i=1;i>sum[i];sum[0]=dp[0]=0;int l=1,r=0;q[++r]=0;for(int i=1;i<=n;i++) sum[i]+=sum[i-1];for(int i=1;i<=n;i++){while(l+1=top(q[l+1],q[l])) l++;dp[i]=dp[q[l]]+(i-q[l]-1+sum[i]-sum[q[l]]-L)*(i-q[l]-1+sum[i]-sum[q[l]]-L); while(l+1<=r&&top(i,q[r])*down(q[r],q[r-1])<=top(q[r],q[r-1])*down(i,q[r])) r--;q[++r]=i;}cout<<dp[n];}

Q2

P3628

A2

\(dp_i=dp_j+(pre_i-pre_j)^2 \times a+(pre_i-pre_j) \times b+c\)

对于决策点 \(j,k\) 且 \(k<j\) 且 \(j\) 优于 \(k\)

\(dp_j+(pre_i-pre_j)^2 \times a+(pre_i-pre_j) \times b+c>dp_k+(pre_i-pre_k)^2 \times a+(pre_i-pre_k) \times b+c\)

\(dp_j+(pre_i-pre_j)^2 \times a+(pre_i-pre_j) \times b>dp_k+(pre_i-pre_k)^2 \times a+(pre_i-pre_k) \times b\)

\(dp_j+(pre_i^2+pre_j^2-2 \times pre_i \times pre_j) \times a+pre_i \times b-pre_j \times b\)

\(dp_j+a \times pre_i^2+a \times pre_j^2-2a \times pre_i \times pre_j+pre_i \times b-pre_j \times b\)

\(dp_j+a \times pre_j^2-2a \times pre_i \times pre_j-pre_j \times b>dp_k+a \times pre_k^2-2a \times pre_i \times pre_k-pre_k \times b\)

\(dp_j+a \times pre_j^2-dp_k-a \times pre_k^2+pre_k \times b-pre_j \times b>2a \times pre_i \times pre_j-2a \times pre_i \times pre_k\)

\(2a \times pre_i \times pre_j-2a \times pre_i \times pre_k<dp_j+a \times pre_j^2-dp_k-a \times pre_k^2+pre_k \times b-pre_j \times b\)

\(2a \times pre_i \times (pre_j-pre_k)<dp_j-dp_k+a \times pre_j^2-a \times pre_k^2+pre_k \times b-pre_j \times b\)

\(2a \times pre_i<(dp_j-dp_k+a \times pre_j^2-a \times pre_k^2+pre_k \times b-pre_j \times b)/(pre_j-pre_k)\)

两边同样具有单调性。

#include#define int long longusing namespace std;const int maxn = 1e6+114;int sum[maxn],q[maxn];int dp[maxn];int n,m,a,b,c;int top(int i,int j){return dp[i]-dp[j]+a*sum[i]*sum[i]-a*sum[j]*sum[j]+sum[j]*b-sum[i]*b;}int down(int i,int j){return sum[i]-sum[j];}signed main(){cin>>n;cin>>a>>b>>c; for(int i=1;i>sum[i];sum[0]=dp[0]=0;int l=1,r=0;q[++r]=0;for(int i=1;i<=n;i++) sum[i]+=sum[i-1];for(int i=1;i<=n;i++){while(l+1<=r&&2*a*sum[i]*down(q[l+1],q[l])<top(q[l+1],q[l])) l++;dp[i]=dp[q[l]]+(sum[i]-sum[q[l]])*(sum[i]-sum[q[l]])*a+(sum[i]-sum[q[l]])*b+c; //val(r,i) < val(r-1,r) r-- while(l+1=top(q[r],q[r-1])*down(i,q[r])) r--;q[++r]=i;}cout<<dp[n];}

Q3

P2900

A3

先把所有土地按照长度排序，各位读者请自行证明排序后最优方案下总是取连续的土地，因而可以转化为序列分割类问题

\(dp_i=dp_j+ \max(j+1,i)(b_i) \times a_i\)

对于决策点 \(j,k\) 且 \(k<j\) 且 \(j\) 优于 \(k\)

\(dp_j+ \max(j+1,i)(b_i) \times a_i<dp_k+ \max(k+1,i)(b_i) \times a_i\)

$ \max(j+1,i)(b_i) \times a_i- \max(k+1,i)(b_i) \times a_i<dp_k-dp_j$

\(a_i \times ( \max(j+1,i)(b_i)- \max(k+1,i)(b_i))<dp_k-dp_j\)

\(a_i<(dp_k-dp_j)/( \max(j+1,i)(b_i)- \max(k+1,i)(b_i))\)

额外用一个线段树维护 \(\max\) 函数即可。

#include#define int long longusing namespace std;const int maxn = 1e6+114;int q[maxn];int dp[maxn];struct Node{int a,b;}chifan[maxn];int tree[maxn*4];void pushup(int cur){tree[cur]=max(tree[cur*2],tree[cur*2+1]); }void build(int cur,int l,int r){if(l==r){tree[cur]=chifan[l].b;return;}int mid=(l+r)/2;build(cur*2,l,mid);build(cur*2+1,mid+1,r);pushup(cur);}int ask(int cur,int lt,int rt,int l,int r){if(rt<l||r<lt){return 0;}if(l<=lt&&rt<=r){return tree[cur];}int mid=(lt+rt)/2;int sum=0;sum=max(sum,ask(cur*2,lt,mid,l,r));sum=max(sum,ask(cur*2+1,mid+1,rt,l,r));return sum;}bool cmp(Node A,Node B){return A.a>n;for(int i=1;i>chifan[i].a>>chifan[i].b;sort(chifan+1,chifan+n+1,cmp);build(1,1,n);dp[0]=0;int l=1,r=0;q[++r]=0;for(int i=1;i<=n;i++){while(l+1<=r&&chifan[i].a*down(i,q[l+1],q[l])<top(q[l+1],q[l])) l++;dp[i]=dp[q[l]]+ask(1,1,n,q[l]+1,n)*chifan[i].a; while(l+1<=r&&top(i,q[r])*down(n,q[r],q[r-1])<=top(q[r],q[r-1])*down(n,i,q[r])) r--;q[++r]=i;}cout<<dp[n];}

Q4

P2120

A4

\(dp_i=dp_j+(\sum_{k=j+1}^{i} p_k \times (x_i-x_k))+c_i\)

\(dp_i=dp_j+(\sum_{k=j+1}^{i} p_k \times x_i-p_k \times x_k)+c_i\)

\(dp_i=dp_j+(\sum_{k=j+1}^{i} p_k \times x_i)-(\sum_{k=j+1}^{i} p_k \times x_k)+c_i\)

\(dp_i=dp_j+x_i \times (\sum_{k=j+1}^{i} p_k)-(\sum_{k=j+1}^{i} p_k \times x_k)+c_i\)

令 $chifan_i=\sum_{j=1}^{i} p_j \times x_j $ 以及 \(pre_i=\sum_{j=1}^{i} p_j\)

\(dp_i=dp_j+x_i \times (pre_i-pre_j)-(chifan_i-chifan_j)+c_i\)

对于决策点 \(j,k\) 且 \(k<j\) 且 \(j\) 优于 \(k\)

\(dp_j+x_i \times (pre_i-pre_j)-(chifan_i-chifan_j)+c_i<dp_k+x_i \times (pre_i-pre_k)-(chifan_i-chifan_k)+c_i\)

\(dp_j-pre_j \times x_i+chifan_j<dp_k-pre_k \times x_i+chifan_k\)

\(dp_j+chifan_j-chifan_k-dp_k<pre_j \times x_i-pre_k \times x_i\)

\(x_i \times (pre_j-pre_k)>(dp_j-dp_k+chifan_j-chifan_k)\)

\(x_i>(dp_j-dp_k+chifan_j-chifan_k)/(pre_j-pre_k)\)

#include#define int long longusing namespace std;const int maxn = 1e6+114;int sum[maxn],q[maxn];int chifan[maxn],c[maxn],p[maxn],x[maxn];int dp[maxn];int n,m;int top(int j,int k){return dp[j]-dp[k]+chifan[j]-chifan[k];}int down(int j,int k){return sum[j]-sum[k];}void init(){for(int i=1;i<=n;i++){sum[i]=sum[i-1]+p[i]; }for(int i=1;i>n;for(int i=1;i>x[i]>>p[i]>>c[i];init();dp[0]=0;int l=1,r=0;q[++r]=0;for(int i=1;i<=n;i++){while(l+1top(q[l+1],q[l])) l++;dp[i]=dp[q[l]]+x[i]*(sum[i]-sum[q[l]])-(chifan[i]-chifan[q[l]])+c[i];while(l+1<=r&&top(i,q[r])*down(q[r],q[r-1])<=top(q[r],q[r-1])*down(i,q[r])) r--;q[++r]=i;}if(p[n]==0) dp[n]-=c[n];cout<<dp[n];return 0;}

总结

一般来说，为了兼顾单调性以及不被贪心暴踩，斜率优化 dp 带有一个平方项

不过只要对于决策点 \(j,k\) 且 \(k<j\) 能表述成 \(f(i) > g(j,k)\) (\(g(j,k)\) 常常为斜率的形式，因此叫做斜率优化)且两边单调的形式，都可以斜率优化，不过有时候这个式子更为灵活，需要变通