笔记：斜率优化DP

lyx1311

2020-08-24 21:43:05

Personal

说明

20 年初学时写了一点，但是咕掉了。于 2021 年 9 月起重写。

下面提到的练习题实际上没有必要全部做完，建议只需要写部分题目的代码。

斜率优化 DP 其他资料：

@辰星凌动态规划—斜率优化DP
@MashiroSky 斜率优化学习笔记

斜率优化DP 基础

此部分的 DP 具有良好的性质，即斜率 k 和横坐标 x 均具有单调性。

例题1 HDU3507 打印文章（ YBT1613 ，LOJ10191 ）

记 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) 。

核心代码：

#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;
}

乘法避免精度误差时，要注意移项后不等号方向是否改变。

练习：

P2120 [ZJOI2007] 仓库建设（ YBT1611 ，LOJ10189 ）
P3195 [HNOI2008] 玩具装箱（ YBT1610 ，LOJ10188 ）
P2365 任务安排（ YBT1607 ，LOJ10185 ）

例题2 CF311B Cats Transport（ YBT1609 ，LOJ10187 ）

此题虽然多了一个维度，但仍然可以斜率优化。关键点有二：

对于代价的计算，可以把猫的结束时间 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) 。

练习：

P4360 [CEOI2004] 锯木厂选址（ YBT1614 ，LOJ10192 ）
CF643C Levels and Regions

例题3 P3628 [APIO2010] 特别行动队（ YBT1612 ，LOJ10190 ）

记 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 和数据范围~~就做完了。

综合练习（较难）：

P2900 [USACO08MAR] Land Acquisition G
CF1083E The Fair Nut and Rectangles
CF1575M Managing Telephone Poles

斜率优化DP 进阶

此部分的 DP 性质稍劣，即斜率 k 和横坐标 x 不一定具有单调性，但仍可以通过二分或维护凸包等方式寻找最优决策点。

例题4 P5785 [SDOI2012] 任务安排（ YBT1608 ，LOJ10186 ）

练习 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

注意到此题数据范围 $|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/) 进行许可。