前言
虽然它的名字很高大上，但是其思想内核非常简单，这篇博客就是用来帮助各位快速入门的
引入
dp优化可以怎么分类？
算法维护决策点集大小，取出无用决策点
Q1
A1
先列出一个朴素的
dp方程:然后我们考虑决策点 \(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 - 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\
然后我们发现这个等式两边全部具有单调性，所以就可以用单调队列维护最优答案
#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
对于决策点 \(j,k\ 且 \(k<j\ 且 \(j\ 优于 \(k\
\(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+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-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-pre_k<dp_j-dp_k+a \times pre_j^2-a \times pre_k^2+pre_k \times b-pre_j \times b\
两边同样具有单调性。
#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
对于决策点 \(j,k\ 且 \(k<j\ 且 \(j\ 优于 \(k\
$ \max(j+1,i(b_i \times a_i- \max(k+1,i(b_i \times a_i<dp_k-dp_j$
\(a_i<(dp_k-dp_j/( \max(j+1,i(b_i- \max(k+1,i(b_i\
#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-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\
\(dp_i=dp_j+x_i \times (pre_i-pre_j-(chifan_i-chifan_j+c_i\
\(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+chifan_j-chifan_k-dp_k<pre_j \times x_i-pre_k \times x_i\
\(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\ 常常为斜率的形式，因此叫做斜率优化且两边单调的形式，都可以斜率优化，不过有时候这个式子更为灵活，需要变通