笔记：斜率优化DP

## 说明 20 年初学时写了一点，但是咕掉了。于 2021 年 9 月起重写。 下面提到的练习题实际上没有必要全部做完，建议只需要写部分题目的代码。 斜率优化 DP 其他资料： - @辰星凌 [动态规划—斜率优化DP](https://www.cnblogs.com/Xing-Ling/p/11210179.html) - @MashiroSky [斜率优化学习笔记](https://www.cnblogs.com/MashiroSky/p/6009685.html) --- ## 斜率优化DP 基础 此部分的 DP 具有良好的性质，即斜率 $k$ 和横坐标 $x$ 均具有单调性。 ### 例题1 [HDU3507 打印文章](http://acm.hdu.edu.cn/showproblem.php?pid=3507)（ [YBT1613](http://ybt.ssoier.cn:8088/problem_show.php?pid=1613) ，[LOJ10191](https://loj.ac/p/10191) ） 记 $f_i$ 表示将前 $i$ 个单词分段的最小花费，$s_i$ 表示 $c_i$ 的前缀和。显然有： $$ \large\begin{aligned} f_i&=\min_{0\le j<i}\{f_j+\text{val}_{j+1,i}\}\\ &=\min_{0\le j<i}\{f_j+\left(\sum_{k=j+1}^ic_k\right)^2+M\}\\ &=\min_{0\le j<i}\{f_j+(s_i-s_j)^2+M\}\\ &=\min_{0\le j<i}\{f_j+s_i^2+s_j^2-2s_is_j+M\}\\ &=s_i^2+M+\min_{0\le j<i}\{f_j+s_j^2-2s_is_j\}\\ \end{aligned} $$ 移项，将只与 $j$ 有关的项移到一边： $$ \large f_{j}+s_j^2=2s_is_j+f_i-s_i^2-M $$ 这个形式像极了一次函数解析式 $y=kx+b$ ，其中 $\begin{cases}y=&f_j+s_j^2\\k=&2s_i\\x=&s_j\\b=&f_i-s_i^2-M\end{cases}$ 且**斜率 $k=2s_i$ 、横坐标 $x=s_j$ 单调递增**，所以我们的任务变成了在所有的 $j(0\le j<i)$ 形成的直线（穿过点 $(s_j,f_j+s_j^2)$ ）中**选择一条截距 $b$ 最小的**。  $$\scriptsize\color{grey}图一$$ 可以理解为把红色虚线不断向上平移遇到的第一个点即为答案。从图中可以看出，B 点在任何情况下都不会是第一个碰到的点。因此我们维护的点应该是下凸的。  $$\scriptsize\color{grey}图二$$ 因为斜率 $k=2s_i$ 单调递增，所以 A 以后都不可能是第一个碰到的点。因此我们维护的点应该像 B-C-D 一样，是**相邻两点连线的斜率单调递增，且最小斜率大于 $k$ 的下凸壳**。每次的最优决策即为维护的点中最左侧的那个。 时间复杂度 $O(n)$ 。 核心代码： ```cpp #define X(o) (s[o]) #define Y(o) (f[o]+s[o]*s[o]) #define K(o) (2*s[o]) #define P(o) (s[o]*s[o]+m) f[0]=0,q[l=r=1]=0;//l==r+1时队列为空 for(int i=1;i<=n;i++){ //踢出队首斜率小于k的点，乘法避免精度误差 while(l<r&&(Y(q[l+1])-Y(q[l]))<=(X(q[l+1])-X(q[l]))*K(i))l++; //转移 f[i]=P(i)+Y(q[l])-K(i)*X(q[l]); //尝试将i点进队并维护下凸壳（相邻两点斜率单调递增），乘法避免精度误差 while(l<r&&(Y(q[r])-Y(q[r-1]))*(X(i)-X(q[r]))>=(Y(i)-Y(q[r]))*(X(q[r])-X(q[r-1])))r--; //i点进队 q[++r]=i; } ``` **乘法避免精度误差时，要注意移项后不等号方向是否改变。** **练习**： 1. [P2120 [ZJOI2007] 仓库建设](https://www.luogu.com.cn/problem/P2120)（ [YBT1611](http://ybt.ssoier.cn:8088/problem_show.php?pid=1611) ，[LOJ10189](https://loj.ac/p/10189) ） 2. [P3195 [HNOI2008] 玩具装箱](https://www.luogu.com.cn/problem/P3195)（ [YBT1610](http://ybt.ssoier.cn:8088/problem_show.php?pid=1610) ，[LOJ10188](https://loj.ac/p/10188) ） 3. [P2365 任务安排](https://www.luogu.com.cn/problem/P2365)（ [YBT1607](http://ybt.ssoier.cn:8088/problem_show.php?pid=1607) ，[LOJ10185](https://loj.ac/p/10185) ） ### 例题2 [CF311B Cats Transport](https://www.luogu.com.cn/problem/CF311B)（ [YBT1609](http://ybt.ssoier.cn:8088/problem_show.php?pid=1609) ，[LOJ10187](https://loj.ac/p/10187) ） 此题虽然多了一个维度，但仍然可以斜率优化。关键点有二： - 对于代价的计算，可以把猫的结束时间 $T_i$ 减去山丘 $H_i$ 的距离，将其记作 $t_i$（ $s_i$ 是它的前缀和）。这样可以认为人在同一时刻光速接走所有猫，避免了距离的影响。 - 按 $t_i$ 对猫排序。一个人的接猫时间一定恰好与至少一只猫的 $t_i$ 相等。所以还是考虑记 $f_{i,k}$ 表示第 $k$ 个人恰好接（排序后）第 $i$ 只猫的最小等待时间，转移枚举他上一个人接哪只猫。 $$ \large\begin{aligned} f_{i,k}&=\min_{0\le j<i}\{f_{j,k-1}+\text{val}_{j+1,i}\}\\ &=\min_{0\le j<i}\{f_{j,k-1}+(i-j)\times t_i+s_j-s_i\}\\ &=\min_{0\le j<i}\{f_{j,k-1}+s_j-t_i\times j+t_i\times i-s_i\} \end{aligned} $$ 移项： $$ \large f_{j,k-1}+s_j=t_i\times j+f_{i,k}-t_i\times i+s_i $$ 有：$\begin{cases}y=&f_{j,k-1}+s_j\\k=&t_i\\x=&j\\b=&f_{i,k}-t_i\times i+s_i\end{cases}$ 。其中斜率 $k=t_i$ 因为排过序所以单调递增。接下来就与例题 1 相同了。 时间复杂度 $O(np)$ 。 **练习**： 4. [P4360 [CEOI2004] 锯木厂选址](https://www.luogu.com.cn/problem/P4360)（ [YBT1614](http://ybt.ssoier.cn:8088/problem_show.php?pid=1614) ，[LOJ10192](https://loj.ac/p/10192) ） 5. [CF643C Levels and Regions](https://www.luogu.com.cn/problem/CF643C) ### 例题3 [P3628 [APIO2010] 特别行动队](https://www.luogu.com.cn/problem/P3628)（ [YBT1612](http://ybt.ssoier.cn:8088/problem_show.php?pid=1612) ，[LOJ10190](https://loj.ac/p/10190) ） 记 $f_i$ 表示由前 $i$ 个人组队的最大修正战斗力，$s_i$ 表示 $x_i$ 的前缀和。 $$ \large\begin{aligned} f_i&=\min_{0\le j<i}\{f_j+\text{val}_{j+1,i}\}\\ &=\min_{0\le j<i}\{f_j+a(s_i-s_j)^2+b(s_i-s_j)+c\}\\ &=\min_{0\le j<i}\{f_j+as^2_j-bs_j-2as_is_j+as_i^2+b_si+c\} \end{aligned} $$ 移项： $$ \large f_j+as_j^2-bs_j=2as_is_j+f_i-as_i^2-bs_i-c $$ 这里要求最大值，所以要使截距最大。观察到斜率 $k=2as_i$ 单调递减（ $a$ 是负数），所以题解区都在说维护上凸壳，相当于一条直线从上往下平移。~~（我偏不）~~我们也可以将柿子两边同时乘以 $-1$ 得： $$ \large -f_j-as_j^2+bs_j=-2as_is_j-f_i+as_i^2+bs_i+c $$ 这不是又变回斜率单调递增、求最小值的情况了吗？于是我们~~直接把例题 1 的代码 copy 过来改一下 define 和数据范围~~就做完了。 **综合练习（较难）**： 6. [P2900 [USACO08MAR] Land Acquisition G](https://www.luogu.com.cn/problem/P2900) 7. [CF1083E The Fair Nut and Rectangles](https://www.luogu.com.cn/problem/CF1083E) 8. [CF1575M Managing Telephone Poles](https://www.luogu.com.cn/problem/CF1575M) --- ## 斜率优化DP 进阶 此部分的 DP 性质稍劣，即斜率 $k$ 和横坐标 $x$ 不一定具有单调性，但仍可以通过二分或维护凸包等方式寻找最优决策点。 ### 例题4 [P5785 [SDOI2012] 任务安排](https://www.luogu.com.cn/problem/P5785)（ [YBT1608](http://ybt.ssoier.cn:8088/problem_show.php?pid=1608) ，[LOJ10186](https://loj.ac/p/10186) ） 练习 3 即为此题弱化版。 还是记 $f_i$ 表示执行前 $i$ 个任务的最小费用，$\text{st}_i$ 表示 $t_i$ 的前缀和。$\text{sc}_i$ 表示 $c_i$ 的前缀和。 这道题的费用由两部分构成，一是完成任务本身所需时间，二是机器启动所需时间。我们把启动时间产生的费用前移，在该批次启动时就计算后续由此次启动产生的所有费用，发现其实一个批次 $(j,i]$ 对总费用的影响其实是 $s\times(\text{sc}_n-\text{sc}_j)$ 。故有： $$ \large\begin{aligned} f_i&=\min_{0\le j<i}\{f_j+\text{val}_{j+1,i}\}\\ &=\min_{0\le j<i}\{f_j+\text{st}_i\times(\text{sc}_i-\text{sc}_j)+s\times(\text{sc}_n-\text{sc}_j)\}\\ &=\min_{0\le j<i}\{f_j-s\times\text{sc}_j-\text{st}_i\times\text{sc}_j+\text{st}_i\times\text{sc}_i+s\times\text{sc}_n\} \end{aligned} $$ 移项，将只与 $j$ 有关的项移到一边： $$ \large f_j-s\times\text{sc}_j=\text{st}_i\times\text{sc}_j+f_i-\text{st}_i\times\text{sc}_i-s\times\text{sc}_n $$ $\begin{cases}y=&f_j-s\times\text{sc}_j\\k=&\text{st}_i\\x=&\text{sc}_j\\b=&f_i-\text{st}_i\times\text{sc}_i-s\times\text{sc}_n\end{cases}$ ，所以仍然是寻找一个决策点，使得直线穿过它时对应的截距最小。维护的点仍然是一个下凸壳。 注意到此题数据范围 $|t_i|\le2^8$ ，因此斜率 $k=\text{st}_i$ 不具有单调性。但是注意到我们的决策点（如图二 B 点），仍然满足其左侧相邻两点的斜率小于 $k$ 而右侧大于 $k$ 。所以我们要在维护的点中二分查找到第一个 $j$ ，使得 $j,j+1$ 点的斜率大于 $k$ ，此时 $j$ 点即为决策点。 时间复杂度 $O(n\log n)$ 。 核心代码： ```cpp #define X(o) (sc[o]) #define Y(o) (f[o]-S*sc[o]) #define K(o) (st[o]) #define P(o) (st[o]*sc[o]+S*sc[n]) f[0]=0,q[l=r=1]=0;//l==r+1时队列为空 for(int i=1,lef,rig,mid;i<=n;i++){ //二分查找决策点，乘法避免精度误差 lef=l,rig=r; while(lef<rig){ mid=(lef+rig)>>1; if(mid==r||Y(q[mid+1])-Y(q[mid])>(X(q[mid+1])-X(q[mid]))*K(i))rig=mid; else lef=mid+1; } //转移 f[i]=P(i)+Y(q[lef])-K(i)*X(q[lef]); //尝试将i点进队并维护下凸壳（相邻两点斜率单调递增），乘法避免精度误差 while(l<r&&(Y(q[r])-Y(q[r-1]))*(X(i)-X(q[r]))>=(Y(i)-Y(q[r]))*(X(q[r])-X(q[r-1])))r--; //i点进队 q[++r]=i; } ``` ### 例题5 [P2497 [SDOI2012] 基站建设](https://www.luogu.com.cn/problem/P2497) 记 $f_i$ 表示传递网络到第 $i$ 个基站的最小花费，通过勾股定理算得代价。 $$ \large\begin{aligned} f_i&=\min_{1\le j<i}\{f_j+\text{val}_{j,i}\}\\ &=\min_{1\le j<i}\{f_j+\dfrac{x_i-x_j}{2\sqrt{r_j}}+v_i\}\\ &=\min_{1\le j<i}\{f_j-\dfrac{x_j}{2\sqrt{r_j}}+\dfrac{x_i}{2\sqrt{r_j}}+v_i\} \end{aligned} $$ 移项： $$ \large\begin{aligned} f_j-\dfrac{x_j}{2\sqrt{r_j}}&=-\dfrac{x_i}{2\sqrt{r_j}}+f_i-v_i\\ \dfrac{x_j}{2\sqrt{r_j}}-f_j&=\dfrac{x_i}{2\sqrt{r_j}}-f_i+v_i \end{aligned} $$ 目标解：$\min\limits_{x_i+r_i\ge m}\{f_i\}$ ，边界：$f_1=v_1$ 。 $\begin{cases}y=&\dfrac{x_j}{2\sqrt{r_j}}-f_j\\k=&x_i\\x=&\dfrac1{2\sqrt{r_j}}\\b=&-f_i+v_i\end{cases}$ ，为使截距最小，维护上凸壳。 发现 $x=\dfrac1{2\sqrt{r_j}}$ 不具有单调性，可以借助 CDQ 分治，先递归左半部分，再用左边的 DP 值（斜率优化）更新右边，然后递归右半部分，返回之前记得按 $x$ 排序方便斜率优化。 时间复杂度 $O(n\log n)$ 。 核心代码： ```cpp //其中n,m,x,r,v如题意所述，q为队列，b为排过序后的下标 int n,m,x[N],r[N],v[N],q[N],b[N],tmp[N]; //p[i]=1/sqrt(r[i])/2，f为DP数组 double p[N],f[N]; #define Y(o) (x[o]*p[o]-f[o]) #define K(o) (x[o]) #define X(o) (p[o]) #define P(o) (v[o]) //计算斜率 double slope(const int u,const int v){return(Y(u)-Y(v))/(X(u)-X(v));} template<class Tp>void tomin(Tp &x,const Tp &y){x=std::min(x,y);} void CDQ(const int l,const int r){ if(l==r){b[l]=l;return;} int mid=(l+r)>>1; CDQ(l,mid); int tail=0; //先将左半部分入队 for(int i=l;i<=mid;i++){ //维护上凸包，上凸包斜率单调递减 while(tail>1&&slope(q[tail],q[tail-1])<=slope(b[i],q[tail]))tail--; q[++tail]=b[i]; } //再更新右半部分 for(int i=mid+1;i<=r;i++){ //因为x已经有序且斜率单调递增，所以直接踢除队尾 while(tail>1&&slope(q[tail],q[tail-1])<=K(i))tail--; tomin(f[i],P(i)-Y(q[tail])+K(i)*X(q[tail])); } CDQ(mid+1,r); //直接使用了<algorithm>库中的merge函数实现归并 std::merge(b+l,b+mid+1,b+mid+1,b+r+1,tmp+l,[](int u,int v){ return X(u)<X(v); }); for(int i=l;i<=r;i++)b[i]=tmp[i]; } ``` 除 CDQ 外还有其他做法，如平衡树、李超线段树等。 **练习**： 9. [P4027 [NOI2007] 货币兑换](https://www.luogu.com.cn/problem/P4027) 10. [BZOJ3963 [WF2011] MachineWorks](https://darkbzoj.tk/problem/3963)（ [Hydro - BZOJ](https://hydro.ac/d/bzoj/p/3963) ） --- ## 斜率优化DP+ ### 例题6 [P4983 忘情](https://www.luogu.com.cn/problem/P4983) 斜率优化 DP + wqs 二分，因为只斜率优化复杂度 $O(nm)$ ，观察到函数具有凸性。证明见 [@register 的题解](https://www.luogu.com.cn/problem/solution/P4983)（文章开了隐藏所以只能在题解区看）。时间复杂度 $O(n\log V)$ ，其中 $V$ 是值域。 **练习**： 11. 用斜率优化 DP + wqs 二分实现例题 2（时间空间均较优于原 $O(np)$ 做法） 12. [P6246 [IOI2000] 邮局 加强版](https://www.luogu.com.cn/problem/P6246) 13. [P5896 [IOI2016] aliens](https://www.luogu.com.cn/problem/P5896) --- ## 备注 作者：lyx1311 最后更新：2022.02.27 本作品采用 [知识共享署名-相同方式共享 4.0 国际许可协议](http://creativecommons.org/licenses/by-sa/4.0/) 进行许可。