前言
斜率優化是一種經典的單調佇列優化型別，雖然它的名字很高大上，但是其思想內核非常簡單，這篇博客就是用來幫助各位快速入門的
提示：本博客以單調佇列的思想理解斜率優化
引入
dp 優化可以怎么分類？
-
資料結構維護決策點集的插入與查找
-
演算法維護決策點集大小，取出無用決策點
而斜率優化 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<bits/stdc++.h>
#define int long long
using 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<=n;i++) cin>>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*(i+sum[i]-1-L)*down(q[l+1],q[l])>=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<bits/stdc++.h>
#define int long long
using 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<=n;i++) cin>>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<=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];
}
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<bits/stdc++.h>
#define int long long
using 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<B.a;
}
int n;
int top(int j,int k){
return dp[k]-dp[j];
}
int down(int i,int j,int k){
return ask(1,1,n,j+1,i)-ask(1,1,n,k+1,i);
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>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<bits/stdc++.h>
#define int long long
using 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;i++){
chifan[i]=chifan[i-1]+p[i]*x[i];
}
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>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+1<=r&&x[i]*down(q[l+1],q[l])>top(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)\) 常常為斜率的形式，因此叫做斜率優化)且兩邊單調的形式，都可以斜率優化，不過有時候這個式子更為靈活，需要變通
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/549674.html
標籤：其他
上一篇：三重境