浅谈斜率优化

# 浅谈斜率优化 ## 问题引入 有一类问题，将n个物品分为连续的若干份（不限制份数），每分一次会产生一个代价（告诉你代价的计算方式），问代价最大/最小是多少。 容易想到，可以用线性DP来解决该问题。令$f[i]$表示选择前$i$个物品的最大/最小代价，则$f[i]=\min\{f[j]+\text{转移代价}\}\quad (1\leq j<i)$。 朴素算法的复杂度为$O(n^2)$ 根据具体问题，我们来研究如何优化这一算法。 ### 一、转移代价为该段物品的价格之和 具体地，序列里的每样物品有一个价值值$a[i]$，我们用$sum[i]$表示$a[1]\sim a[i]$的和。则$f[i]=\min\{f[j]+sum[i]-sum[j]\}\quad (1\leq j<i)$。 我们用一个变量记录$i$之前所有$f[j]-sum[j]$的最小值，即可实现$O(1)$转移。总复杂度为$O(n)$。 现在难度加大，要求每段最多不超过k个物品。这时我们用**单调队列**维护一个$k$区间内$f[j]-sum[j]$的最小值即可。相信大家都会。 //当然，读到这里大家可能已经反应过来，这个sb的问题根本不需要DP。~~（是不是感觉被骗了~~（逃 ### 二、转移代价为该段物品的价格之和的平方 即$f[i]=\min\{f[j]+(sum[i]-sum[j])^2\}\quad (1\leq j<i)$。 我们把平方拆开，得到$f[i]=\min\{f[j]+sum[i]^2-2*sum[i]*sum[j]+sum[j]^2\}$ 中间有一项$2*sum[i]*sum[j]$。单调队列懵逼了。 **事实上，只要状态转移方程中含有既有$sum[i]$，又有$sum[j]$的项（如$sum[i]*sum[j]$），那么我们就无法使用上述的方法优化。**注意，这里的“项”指的是一个单独的项，而$sum[i]-sum[j]$就不算，因为它是两项。当然，根据题目描述的不同，$sum$数组有可能被替换为其他数组。 这时，我们今天的主角：**斜率优化**就要登场了。 ## 状态转移方程的化简与改写 斜率优化算法最重要的一步，就是要将状态转移方程**改写**为$y=kx+b$的形式。而这一算法主要的难点就在于，**对于一个复杂的状态转移方程，我们将哪些项将作为$y$，哪些项最为$k$和$x$，哪些项作为$b$。** 这既需要掌握普遍性的套路和方法，又需要不断的练习，培养敏感度、熟练度，从而快速、准确地改写状态转移方程。 我们以[P3195 玩具装箱](https://www.luogu.org/problemnew/show/P3195)为例： 我们很容易列出状态转移方程：$f[i]=\min\{f[j]+(sum[i]-sum[j]+i-j-L-1)^2\}$。 先把min去掉，初步整理得：$f[i]=f[j]+[(sum[i]+i)-(sum[j]+j)-L-1]^2$ 为了便于表述，我们让L++，同时令$s[k]=sum[k]+k$。则方程可进一步化简为：$f[i]=f[j]+(s[i]-s[j]-L)^2$ 将平方项展开，得到：$f[i]=f[j]+s[i]^2+(s[j]+L)^2-2*s[i]*(s[j]+L)$ 到这里，方程就化简地差不多了。接下来看怎样把方程改写为$y=kx+b$的形式： ### 我们令既有$sum[i]$，又有$sum[j]$的项为$kx$；令含有$f[j]$的项以及其他所有含有$sum[j]$的项为$y$；令$f[i]$和剩余所有的项为$b$ 更具体地，在$kx$里，包含$sum[j]$的项是$x$，其他的是$k$。 则原方程可化为：$f[j]+(s[j]+L)^2=2*s[i]*(s[j]+L)+f[i]-s[i]^2$ 其中： - $y=f[j]+(s[j]+L)^2$ - $k=2*s[i]$ - $x=(s[j]+L)$ - $b=f[i]-s[i]^2$ ## 斜率优化的数学推导 现在，我们按照上述的$x$和$y$建立一个**平面直角坐标系**。则我们需要最小化$f[i]$，就是最小化该函数的**截距**（截距：就是$y=kx+b$中的$b$）。 由于$k=2*s[i]$的值不随$j$的变化而变化，因此该函数图像的**斜率一定**。这时我们可以把选择状态的过程想象为一条斜率一定的直线在坐标系里**向上平移**的过程。而因为每个不同的$j$会带来不同的$x$和$y$的取值，因此**每个决策点都对应了平面直角坐标系里的一个点**。为了使我们这条函数图像的截距最小，我们在向上平移的过程中**一定先选第一个碰到的点**。  对于任意三个决策点$A(x_1,y_1)$，$B(x_2,y_2)$，$C(x_3,y_3)$，我们不妨设$x_1<x_2<x_3$。我们发现$B$能成为最优决策当且仅当： $\frac{y_2-y_1}{x_2-x_1}<\frac{y_3-y_2}{x_3-x_2}$。 即$AB$段的斜率小于$BC$段的斜率。通俗地讲，我们应该维护“连接相邻两点的线段斜率”单调递增的一个“下凸壳”，只有这个下凸壳的顶点才有可能成为最优决策。**实际上，对于一条斜率为$k$的直线，若某个顶点左侧线段的斜率比$k$小，右侧线段的斜率比$k$大，则该顶点就是最优决策。**换言之，只要找到了这样一个点，我们就得到了使截距最小化的那个决策$j$。 ## 单调队列维护凸壳 在本题中，有两个隐藏的条件： 1. 横坐标$x$，即$(s[j]+L)$递增。 2. 相邻两点的线段斜率，即$2*s[i]$也是递增的。 因此我们可以用一个**单调队列**来维护前文所述的这样一个“凸壳”。对于每个状态变量$i$： 1. 检查队头的两个决策变量$q[l]$和$q[l+1]$，若他们的斜率$\frac{Y(q[l+1])-Y(q[l])}{X(q[l+1])-X(q[l])}<=k$（这里$k$、$x$、$y$就是前面改写状态转移方程得到的$k=2*s[i]$，$x=(s[j]+L)$，$y=f[j]+(s[j]+L)^2$），则将队头$q[l]$弹出。 2. 直接取出队头$j=q[l]$为最优决策，计算出$f[i]$。 3. 把新决策$i$从队尾插入。在插入之前，若三个决策点$q[r-1]$，$q[r]$，$i$不满足斜率单调递增（不满足下凸性，即$q[r]$是无用决策），则直接从队尾让$q[r]$出队，继续检查新的队尾。 由于每个元素最多入队、出队一次，因此整个算法的时间复杂度为$O(n)$。 ### 给出例题（玩具装箱）的代码： ```cpp //P3195 #include <bits/stdc++.h> #define int long long using namespace std; const int MAXN=5e4+5; int n,L,s[MAXN],q[MAXN],f[MAXN]; signed main() { // freopen("","r",stdin); // freopen("","w",stdout); ios_base::sync_with_stdio(0); //syn加速 cin>>n>>L; L++; for(int i=1;i<=n;i++) { cin>>s[i]; s[i]+=s[i-1]; } for(int i=1;i<=n;i++) s[i]+=i; q[1]=0; int l=1,r=1; for(int i=1;i<=n;i++) { while(l<r && (f[q[l+1]]+(s[q[l+1]]+L)*(s[q[l+1]]+L)-(f[q[l]]+(s[q[l]]+L)*(s[q[l]]+L))) <=(2*s[i])*(s[q[l+1]]-s[q[l]])) l++; int j=q[l]; f[i]=f[j]+(s[i]-s[j]-L)*(s[i]-s[j]-L); while(l<r && (f[q[r]]+(s[q[r]]+L)*(s[q[r]]+L)-(f[q[r-1]]+(s[q[r-1]]+L)*(s[q[r-1]]+L))) *(s[i]-s[q[r]]) >=(f[i]+(s[i]+L)*(s[i]+L)-(f[q[r]]+(s[q[r]]+L)*(s[q[r]]+L))) *(s[q[r]]-s[q[r-1]])) r--; q[++r]=i; } cout<<f[n]<<endl; return 0; } ``` ## 思考：不同的情况如何应变 以上讲的就是“斜率优化DP”的主要内容了。但是考试一定不会考模板题，因此我们接下来简单谈谈本题的不同变种及其应对方法。 ### 一、相邻两个决策点的斜率不递增 这种情况下，我们无法保证小于等于当前斜率的决策点$j$一定也小于下一个状态的斜率。因此不能进行“弹掉队首元素”这一步。但是这不影响我们维护一个下凸壳，因此我们可以在单调队列（下凸壳）内进行**二分查找**，找到第一个使该决策点和下一个决策点构成的线段斜率$>k$的决策点，即为当前最优决策。 ### 二、每个决策点横坐标不递增 这意味着要在凸壳任意位置动态插入顶点、动态查询，我们可以使用**平衡树**来维护凸壳。具体实现难度较大，本文不讨论，有兴趣的读者可以自己查阅资料。 ### 三、决策点无顺序 最后，不要忘记，我们之前讨论的一切前提建立在决策点有序的基础上，即本文一开始说的，将$n$个物品分为连续的若干份。但如果物品之间本身没有顺序，就不能进行斜率优化DP了。这时往往需要用**贪心**的方法对决策点进行排序。 ## 祝学习顺利！