斜率优化dp总结

首先以玩具装箱为例: 题目链接:[玩具装箱](https://www.lydsy.com/JudgeOnline/problem.php?id=1010) 设${f[i]}$为到前i个玩具的最小价值 易得:${f[i]=min(f[i],f[j]+(a[i]-b[j])^2)}$ 其中${a[i]=sum[i]+i,b[i]=sum[i]+i+l+1}$; 但时间复杂度为O(n^2),需要优化; 将上式展开,得: ${f[i]=f[j]+a[i]^2-2*a[i]*b[j]+b[j]^2}$ 可以将${2*a[i]}$ 看为斜率,${(b[j],f[j]+b[j]^2)}$ 看成平面直角坐标系上的点 因此就把上述该式转为形如y=kx+b的式子 我们要让f[i]最小, 所以就要找一个合法的j,使得该直线在y轴上的截距最小  当枚举到i点时,最优的点组成了一个下凸包 显然,凸包中相邻两点的斜率单调递增, 目标直线2*a[i]也是单调递增 根据线性规划知识易知,满足最优pj的点一定是第一个 第一个slope(Pj,Pj+1)>2*a[i]的点 因为加入slope(Pj,Pj+1) <= 2*a[i],我们可以通过将Pj移动到Pj+1来让答案更优 那么如何维护凸包??? 单调队列: ```cpp 1.while(head < tail && slope(q[head],q[head + 1]) < 2 *a(i))++ head; 2.f[i] = f[q[head]] + (a(i) - b(q[head])) * (a(i) - b(q[head])); 3.while(head < tail && slope(i,q[tail - 1]) < slope(q[tail - 1],q[tail])) -- tail; 4.q[++ tail] = i; ``` 解释: 若slope(Pj,Pj+1)<2*a[i],显然Pj不是最优直接删掉 因为目标直线斜率单调递增，所以当前删去的Pj 一定对之后的dp[i]也不是最优，不会造成影响 而操作3的理由如下：  显然，满足操作3的要求时，P_tail凸包内部，一定不是最优，因此可以删去 以上也就是斜率优化的基本思想. 放上该题的代码: ```cpp #include<bits/stdc++.h> #define int long long using namespace std; inline int read() { int X = 0,w = 0;char ch = 0; while(!isdigit(ch)){w |= ch == '-';ch = getchar();} while(isdigit(ch)){X = X * 10 + ch - '0';ch = getchar();} return w ? -X:X; } const int N = 5e5 + 101; int f[N], sum[N]; int n, l, q[N]; double a(int x){return sum[x] + x;} double b(int x){return sum[x] + x + l + 1;} double X(int x){return b(x);} double Y(int x){return f[x] + b(x) * b(x);} double slope(int i,int j){return (Y(i) - Y(j)) / (X(i) - X(j));} signed main() { n = read();l = read(); for(int i = 1;i <= n;i ++) scanf("%lld",&sum[i]),sum[i] += sum[i - 1]; int head = 1, tail = 1; for(int i = 1;i <= n;i ++) { while(head < tail && slope(q[head],q[head + 1]) < 2 * a(i)) ++ head; f[i] = f[q[head]] + (a(i) - b(q[head])) * (a(i) - b(q[head])); while(head < tail && slope(i,q[tail - 1]) < slope(q[tail - 1],q[tail])) -- tail; q[++ tail] = i; } cout << f[n]; } ``` ### 一些例题: 1.APIO特别行动队: 原题链接:[特别行动队](https://www.lydsy.com/JudgeOnline/problem.php?id=1911) 我们设${f[i]}$为到i的最大价值; 易得,${f[i]=min(f[j]+a*x*x+b*x+c,f[i])}$; 其中x为${sum[i]-sum[j]}$ 考虑斜率优化: 我们将上述dp方程展开就可已得到: ${(2*sum[i]+b)*sum[j]+???=f[j]+a*sum[j]^2}$ 具体怎么推导就不细说了: 将${2*sum[i]+b}$看作斜率,${(sum[i],f[i]+a*sum[j]^2)}$看为点 维护一个下凸包即可,具体的直接套板子就行 详见代码: ```cpp #include<bits/stdc++.h> #define int long long using namespace std; inline int read() { int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch)){X=X*10+ch-'0';ch=getchar();} return w?-X:X; } const int N=2e6+101; int n,a,b,c; int val[N],f[N],sum[N],q[N]; template<typename T>T Max(T a,T b){return a>b?a:b;} double X(int i){return sum[i];} double Y(int i){return f[i]+a*sum[i]*sum[i];} double slope(int i,int j){return (Y(j)-Y(i))/(X(j)-X(i));} int Val(int x){return a*x*x+b*x+c;} signed main() { n=read();a=read();b=read();c=read(); for(int i=1;i<=n;i++)val[i]=read(); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+val[i]; int head=1,tail=1; for(int i=1;i<=n;i++) { while(head<tail&&slope(q[head],q[head+1])>2*a*sum[i]+b)++head; f[i]=f[q[head]]+Val(sum[i]-sum[q[head]]); while(head<tail&&slope(i,q[tail-1])>slope(q[tail-1],q[tail]))--tail; q[++tail]=i; } printf("%lld\n",f[n]); return 0; } ``` 2.ZJOI仓库建设: 题目链接:[仓库建设](https://www.luogu.org/problemnew/show/P2120) 我们设${f[i]}$为到i点的最小价值 易得到: ${f[i]=min(f[i],f[j]+x[i]*(sum1[i]-sum1[j])-(sum2[i]-sum2[j]+c[i])}$ 其中,${sum1[i]}$为1到i的${p[i]}$前缀和 ${sum2[i]}$为1到i的${p[i]*c[i]}$的前缀和 将上式转化,得: ${x[i]*sum1[j]+???=f[i]+sum2[i]}$ 依旧套上面的板子即可: 详见代码: ```cpp #include<bits/stdc++.h> #define ll long long using namespace std; inline int read() { int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch)){X=X*10+ch-'0';ch=getchar();} return w?-X:X; } const int N=1e6+101; ll x[N],p[N],c[N],sum1[N],sum2[N],f[N],q[N]; int n; double X(int i){return sum1[i];} double Y(int i){return f[i]+sum2[i];} double slope(int i,int j){return (Y(i)-Y(j))/(X(i)-X(j));} ll Val(int l,int r) { return x[r]*(sum1[r]-sum1[l-1])-sum2[r]+sum2[l-1]+c[r]; } int main() { n=read(); for(int i=1;i<=n;i++){ x[i]=read();p[i]=read();c[i]=read(); } for(int i=1;i<=n;i++){ sum1[i]=sum1[i-1]+p[i];sum2[i]=sum2[i-1]+p[i]*x[i]; } int head=1,tail=1; for(int i=1;i<=n;i++) { while(head<tail&&slope(q[head],q[head+1])<x[i])++head; f[i]=f[q[head]]+Val(q[head]+1,i); while(head<tail&&slope(q[tail],q[tail-1])>slope(q[tail],i))--tail; q[++tail]=i; } cout<<f[n]; } ``` 3.征途 [征途](https://www.lydsy.com/JudgeOnline/problem.php?id=4518) 首先直接求方差显然不好求, 于是可以先化简方差的式子 设分的每一段和为x 所以: ${s^2=m^2*(1/m)*((x_1-x)^2+......(x_m-x)^2)}$ 于是: ${s^2=m*(x_1^2-2*x_1*x+x^2+.......x_m-2*x_m*x+x^2)}$ 将m乘进去: ${s^2=m*(x_1^2+.......+x_m^2)-2*m*x*sum+sum^2}$ 其中${sum}$为${1-n}$的总和 这样我们只需让分的每一段的和的平方的总和最小即可; 答案即为$f[m][n]*m-sum[n]*sum[n]$; 直接dp是${O(n^2m)}$需要优化 考虑斜率优化: 在枚举${f[j][i]}$最优何时取到可以斜率优化; 因此:设$z=j-1$ 所以: $f[j][i]=f[z][k]+(sum[i]-sum[k])^2$ 展开: $2*sum[i]*sum[k]+???=f[z][k]+sum[k]^2$ 把$2*sum[i]$看为斜率,$(sum[k],f[z][k]+sum[k]^2)$ 看成一个点 每次枚举$j$时直接${O(n)}$的维护下凸包即可; 其他的就是套斜率优化的板子即可; ``` #include<bits/stdc++.h> #define int long long using namespace std; inline int read() { int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch)){X=X*10+ch-'0';ch=getchar();} return w?-X:X; } //f[i]=min(f[i],f[j]+(sum[i]-sum[j])^2; const int N=4005; int f[N][N],sum[N],q[N],z,n,m; double X(int i){return sum[i];} double Y(int i){return f[z][i]+sum[i]*sum[i];} double slope(int i,int j){return (Y(j)-Y(i))/(X(j)-X(i));} int pi(int x){return x*x;} signed main() { n=read();m=read(); for(int i=1;i<=n;i++) sum[i]=read(),sum[i]+=sum[i-1]; f[0][0]=0; for(int i=1;i<=n;i++)f[1][i]=sum[i]*sum[i]; for(int j=2;j<=m;j++) { int head=1,tail=1; z=j-1; memset(q,0,sizeof(q)); for(int i=1;i<=n;i++) { while(head<tail&&slope(q[head],q[head+1])<2*sum[i])++head; f[j][i]=f[z][q[head]]+pi(sum[i]-sum[q[head]]); while(head<tail&&slope(q[tail],q[tail-1])>slope(q[tail-1],i))--tail; q[++tail]=i; } } cout<<f[m][n]*m-sum[n]*sum[n]; } ``` 4.土地购买 [土地购买](https://www.lydsy.com/JudgeOnline/problem.php?id=1597) 这题好像无法直接dp; 没关系,我们转化一下即可 首先我们需要由题意知道: 假如一个矩形被另一个矩形所嵌套 则这个矩形对答案一定没有贡献; 我们首先将这些矩形中没有用的全部删去 将x为第一关键字从小到大排序,y为第二关键字从大到小排序; 于是我们得到的序列一定是x单增,y单减的序列 于是得到方程$f[i]=min(f[i],f[j]+x[i]*y[j+1]);$ 套斜率优化即可, 具体怎么优化就不再赘述了. 放上本题代码: ``` #include<bits/stdc++.h> #define int long long using namespace std; inline int read() { int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch)){X=X*10+ch-'0';ch=getchar();} return w?-X:X; } const int N=2e6+101; struct node{ int x,y,flag; bool operator < (const node &a)const{ return x==a.x?y<a.y:x<a.x; } }b[N],c[N]; int n,cnt,q[N],f[N],e[N],maxn; bool cmp(node a,node b){return a.x==b.x?a.y>b.y:a.x<b.x;} double X(int i){return -c[i+1].y;} double Y(int i){return f[i];} double slope(int i,int j){return (Y(i)-Y(j))/(X(i)-X(j));} #define lowbit(i) i&-i void update(int x) { ++x; for(int i=x;i<=maxn+1;i+=lowbit(i)) e[i]++; } int query(int x) { int sum=0;++x; for(int i=x;i;i-=lowbit(i)) sum+=e[i]; return sum; } signed main() { n=read(); for(int i=1;i<=n;i++) b[i].x=read(),b[i].y=read(),maxn=max(maxn,b[i].y); sort(b+1,b+n+1); for(int i=n;i>=1;i--) { if((n-i)-query(b[i].y-1)>0)b[i].flag=1; update(b[i].y); } for(int i=1;i<=n;i++) if(!b[i].flag)c[++cnt]=b[i]; int head=1,tail=1; for(int i=1;i<=cnt;i++) { while(head<tail&&slope(q[head],q[head+1])<c[i].x)++head; f[i]=f[q[head]]+c[i].x*c[q[head]+1].y; while(head<tail&&slope(q[tail],q[tail-1])>slope(q[tail-1],i))--tail; q[++tail]=i; } cout<<f[cnt]; } ``` ------------ 小结: 1.斜率优化的数的方式是比较好理解的，我们每次找到动态规划的状态转移方程后就可以直接转换 2.斜率优化只适用于具有单调性的转移方程，即最后简化后的等式左右中的一方必定有一个是给定单调的函数，譬如前缀和。 3.每次斜率优化都要设更优解的自变量，然后用更优解来维护斜率 4.保证储存斜率的队列单调 5.很值得注意到一点，对于初学者而言我们可能会想，为什么可以把斜率转换成这样的形式，其实不然，斜率的形式并不唯一，我们不需要去刻意仿照别人的斜率等式，只要二者等价，即都可以求出正解 6.注意正负，可以看见斜率的会有除法运算，记得不等式除负数时要变号（可能就我这么傻，不会变号），不然公式推错那就GG了 7.最后就是要在做题中理解斜率优化的妙用，可以参考一下他人的代码，或许会大有启发。 8.斜率优化关键在于式子的推导,只要推导正确其他就是板子了