【学习笔记】动态规划—斜率优化DP（超详细）

\(update\ 2020.6.19:\) 临近退役，终于来修锅啦QAQ（更正基础概念上的错误；\(\text{Latex}\) 规范化；重新排版；增加标题号；添加【关于单调性的研究】；添加 \(\text{CDQ}\) 维护斜率优化的例子）

【前言】

第一次写这么长的文章。

写完后对斜优的理解又加深了不少（\(update\ 2020.6.19:\) 回过头来看这句话满是讽刺啊，明明这时候连基本的概念都没有理清....）。

本文讲解较详，只要耐心读下去，相信大部分 \(\text{OIer}\) 都能看懂。

斜率优化 \(\text{dp}\)，顾名思义就是利用斜率相关性质对 \(\text{dp}\) 进行优化。

斜率优化通常可以由两种方式来理解，需要灵活地运用数学上的数形结合,线性规划思想。

对于这样形式的 \(\text{dp}\) 方程：\(dp[i]=Min/Max(a[i]?b[j]+c[j]+d[i])\)，其中 \(b\) 严格单调递增。

该方程的关键点在于 \(a[i]*b[j]\) 这一项，它既有 \(i\) 又有 \(j\)，于是单调队列优化不再适用，可以尝试使用斜率优化。

一.【理解方式】

以 【模板】 玩具装箱 \(\text{toy [P3195]}\) 为例，两种斜优的理解方式。

设 \(S[n]=\sum_{i=1}^n(C[i]+1)\)，用 \(dp[i]\) 表示装好前 \(i\) 个的最小花费，则转移方程为：\(dp[i]=min(dp[j]+(S[i]?S[j]-1-L)^2)\)。

为方便描述，将 \(\text{L}\) 提前加 \(1\)，再把 \(min\) 去掉，得到状态转移方程：\(dp[i]=dp[j]+(S[i]?S[j]-L)^2\)。

化简得：\(dp[i]=S[i]^2-2S[i]L+dp[j]+(S[j]+L)^2-2S[i]S[j]\)

1.【代数法（数形结合）】

只含 \(\text{L}\) 的项对于每一个 \(i\) 的择优筛选过程都是完全一样的值，只含 \(Function(i)\) 的项在一次 \(i\) 的择优筛选过程中不变，含 \(Function(j)\) 的项可能会不断变化（在本题中表现为为严格单增）。
我们以此为划分依据，把同类型的项用括号括起来，即：\(dp[i]=(-2S[i]S[j])+(dp[j]+(S[j]+L)^2)+(S[i]^2-2S[i]L)\)

(1).【维护一个凸包】

设 \(j_1,j_2\) \((0 \leqslant j_1 为 \(i\) 的两个决策点，且满足决策点 \(j_2\) 优于 \(j_1\)，
有：\((-2S[i]S[j_2])+(dp[j_2]+(S[j_2]+L)^2)+(S[i]^2-2S[i]L) \leqslant (-2S[i]S[j_1])+(dp[j_1]+(S[j_1]+L)^2)+(S[i]^2-2S[i]L)\)

即：\((-2S[i]S[j_2])+(dp[j_2]+(S[j_2]+L)^2) \leqslant (-2S[i]S[j_1])+(dp[j_1]+(S[j_1]+L)^2)\)

划重点：此处移项需要遵循的原则是：参变分离。将 \(Function(i)\) 视作未知量，用 \(Function(j)\) 来表示出 \(Function(i)\) 。

移项得：\(-2S[i](S[j_2]-S[j_1]) \leqslant (dp[j_1]+(S[j_1]+L)^2)-(dp[j_2]+(S[j_2]+L)^2)\)
\(\because C[j] \geqslant 1\)
\(\therefore S[j+1] > S[j]\)
\(又 \because j_2 > j_1\)
\(\therefore S[j_2]-S[j_1]>0\)
\(\therefore 2S[i] \geqslant \frac {(dp[j_2]+(S[j_2]+L)^2)-(dp[j_1]+(S[j_1]+L)^2)} {S[j_2]-S[j_1]}\)
设 \(Y(j)=dp[j]+(S[j]+L)^2,X(j)=S[j]\)，
即 \(2S[i] \geqslant \frac {Y(j_2)-Y(j_1)} {X(j_2)-X(j_1)}\)

显然等式右边是一个关于点 \(P(j_2)\) 和 \(P(j_1)\) 的斜率式，其中 \(P(j)=(X(j),Y(j))=(S[j],dp[j]+(S[j]+L)^2)\)。

也就是说，如果存在两个决策点 \(j_1,j_2\) 满足 \((0 \leqslant j_1，使得不等式 \(\frac {Y(j_2)-Y(j_1)} {X(j_2)-X(j_1)} \leqslant 2S[i]\) 成立，或者说 使得 \(P(j_2),P(j_1)\) 两点所形成直线的斜率小于等于 \(2S[i]\)，那么决策点 \(j_2\) 优于 \(j_1\)。

划重点：斜优灵活多变，细节麻烦也多，所以尽量将问题模式化。
比如这里的最终公式，尽量化为 \(\frac {(j)-(j')} {(j)-(j')}\) 的形式，而不是 \(\frac {(j)-(j')} {(j')-(j)}\) ，虽然直接做一般也不会出什么问题，但这样子可以方便理解，方便判断凸包方向等等。

假设有酱紫的三个点 \(P(j_1),P(j_2),P(j_3)\)，\(k_1,k_2\) 为斜率，如下图所示情况（三点分别为 \(A,B,C\)）：

显然有 \(k_2 < k_1\)。设 \(k_0=2S[i]\)，由上述结论可知：

\((a).\) 若 \(k_1 \leqslant k_0\)，则 \(j_2\) 优于 \(j_1\) 。反之，若 \(k_1 > k_0\)，则 \(j_1\) 优于 \(j_2\) 。
\((b).\) 若 \(k_2 \leqslant k_0\)，则 \(j_3\) 优于 \(j_2\) 。反之，若 \(k_2 > k_0\)，则 \(j_2\) 优于 \(j_3\) 。

于是这里可以分三种情况来讨论：

\((1).\) \(k_0 < k_2 < k_1\)。由 \((a),(b)\) 可知：\(j_1\) 优于 \(j_2\) 优于 \(j_3\) 。
\((2).\) \(k_2 \leqslant k_0 < k_1\)。由 \((a),(b)\) 可知：\(j_1\) 和 \(j_3\) 均优于 \(j_2\)。
\((3).\) \(k_2 < k_1 \leqslant k_0\)。由 \((a),(b)\) 可知：\(j_3\) 优于 \(j_2\) 优于 \(j_1\) 。

可以发现，对于这三种情况，\(j_2\) 始终不是最优解，于是我们可以将 \(j_2\) 从候选决策点中踢出去（删除），只留下 \(j_1\) 和 \(j_3\)，删后的情况如下图所示：

我们要对某一个问题的解决方案进行优化改进，无非就是关注两个要点：正确性和高效性（很多时候高效性都体现为单调性）。

酱紫做的正确性是毋庸置疑的，因为在 \(j_1\) 和 \(j_3\) 其中必定有一个比 \(j_2\) 更优，所以删除 \(j_2\) 对答案没有任何影响。

那么高效性呢？自己在脑子里面 \(yy\) 一下，在一个坐标系的第一象限中（本题中 \(X(j)\) 和 \(Y(j)\)均大于等于 \(0\)，至于为什么这里要说等于，下面会提到），有若干个离散的点，任取三点，如果左边斜率大于右边斜率，则形成了上述情况，必定会删点，因而消除这种情况。所以将最后留下来的点首位相连，其形成的各个线段斜率从左到右必定是单调递增的（有可能非严格递增，这个问题之后再讨论）。

如果学习过计算几何相关知识，会意识到这个过程其实与求凸包算法是类似的。（顺手丢一个广告：）

实际上在图中选取最靠左下面、下面、右下面的点首位相连，就是最后留下来的点了，它们形成了一个下凸包，即凸包（又名凸壳）的下半部分（不严谨的讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边形，它能包含点集中所有的点——摘自百度百科）。

维护出的图形如下图所示：

可以尝试在凸包围起来的区域内任意取一点，其必定能在包围圈上找到两个点使得该点可被删除。如上 \(\text{L}\) 点，它与 \(D,E\) 两点形成了一个可删点图形。

注意：图中 \(C,D,E\) 故意画成了三点一线，而实际上点 \(D\) 是可以删去的，且严格凸包不允许存在这种情况。关于去重的细节问题后面会提到。

同理，如果把不等式 \(\frac {Y(j_2)-Y(j_1)} {X(j_2)-X(j_1)} \leqslant k_0[i]\) 改为 \(\frac {Y(j_2)-Y(j_1)} {X(j_2)-X(j_1)} \geqslant k_0[i]\)，那么维护出来的就是一个上凸包。

(2).【寻找最优决策点】

在一次决策点的寻找中，易知下凸包点集里总会存在一点，使得它与左邻点形成的斜率小于等于 \(k_0\) ，与右邻点形成的斜率大于 \(k_0\) 。

例如上图中的 \(E\) 点，设 \(k_4 \leqslant k_0 < k_5\) 由于凸包上面的斜率呈单增态，那么有：\(k_1 < k_2 < k_3 < k_4 \leqslant k_0 < k_5 < k_6 < k_7\)，所以决策点 \(E\) 优于其他所有点，即 \(E\) 就是 \(dp[i]\) 的最优决策点。

如果暴力查找的话，就是从第一个点开始向后扫描，找到第一个斜率大于 \(k_0\) 的线段，其左端点即为最优决策点。由于凸包上的斜率依次递增，可以二分快速得到这个点。

2.【线性规划】

先回顾一下模板题的 \(\text{dp}\) 方程：\(dp[i]=S[i]^2-2S[i]L+dp[j]+(S[j]+L)^2-2S[i]S[j]\)。

对其进行移项变化，变成形如 \(y=kx+b\) 的点斜式。
划重点：移项要遵循的原则是：把含有 \(function(i)*function(j)\) 的表达式看作斜率 \(k_0\) 乘以未知数 \(x\)，含有 \(dp[i]\) 的项必须要在 \(b\) 的表达式中，含有 \(function(j)\) 的项必须在 \(y\) 的表达式中。如果未知数 \(x\) 的表达式单调递减，最好让等式两边同乘个 \(-1\)，使其变为单增。

至于为什么说要让 \(x\) 的表达式单增，emm...其实是为了让一些较简单的问题模式化，不易出错，如果你非要单减，可以尝试倒序枚举，至于是否正确，具体实现需要注意的玄学问题等等，因为觉得太麻烦没有细想，我也不清楚会遇到什么问题。

例如此题，原 \(\text{dp}\) 方程可化为：
\((2S[i])S[j]+(dp[i]-S[i]^2+2S[i]L)=(dp[j]+(S[j]+L)^2)\)

其中 \(k_i=2S[i],\) \(x_i=S[j],\) \(b_i=dp[i]-S[i]^2+2S[i]L,\) \(y_i=dp[j]+(S[j]+L)^2\)。

其实也可以化为：
\((2S[i])(S[j]+L)+(dp[i]-S[i]^2)=(dp[j]+(S[j]+L)^2)\)
其中 \(k_i=2S[i],\) \(x_i=S[j]+L,\) \(b_i=dp[i]-S[i]^2,\) \(y_i=dp[j]+(S[j]+L)^2\)。

还可以化为 \(...\)

\(...\)

只要满足上述移项原则，对答案是没有任何影响的。

这里以第一种形式为例，先画出草图：

(1).【高中数学知识】

我们的目的是求出一个最优决策点 \(j\) 使得 \(dp[i]\) 最小，又因为 \(b[i]=dp[i]-S[i]^2\) ，所以就是要找到某个点使这条直线经过它时算出来的 \(b\) 最小，即是高中数学课本上的线性规划问题。

(2).【寻找最优决策点】

如图所示，点 \(E\) 即为最优决策点。显然，这个使得 \(b\) 最小的最优决策点位于下凸包点集中，且与上述代数法求得的点一致。

3.【两种思考方式的结合】

强烈推荐用线性规划思想主导思考过程，因为图形的变幻较直观，更重要的是：在某某变量不满足单调性时，通过图形可以迅速做出判断并改变策略（在后面【关于单调性的研究】中会详细解释）。

而代数法通常在不便于识别方程特征时起一个转换思维方向的作用，因为有些题可能会直接出现 \(\frac{Y(j)-Y(j')}{X(j)-X(j')}\) 的形式，需要通过一系列代数推导后再绘草图模拟决策。

二.【维护凸包】

实际上只要让维护的凸包方向相同，两种思考方式的代码是一模一样的。

用单调队列维护凸包点集，操作分三步走：
\((1).\) 进行择优筛选时，在凸包上找到最优决策点 \(j\) 。
\((2).\) 用最优决策点 \(j\) 更新 \(dp[i]\) 。
\((3).\) 将 \(i\) 作为一个决策点加入图形并更新凸包（如果点 \(i\) 也是 \(dp[i]\) 的决策点之一，则需要将 \((3)\) 换到最前面）。

在本题中步骤 \((3)\) 的具体操作为：判断当队尾的点与点 \(i\) 形成可删点图形时，出队直至无法再删点，然后将 \(i\) 加入队列。

在判断可删图形时有两种方法（以 下凸包 为例），一种是 slope(Q[t-1],Q[t])<=slope(Q[t],i)，另一种是 slope(Q[t-1],Q[t])<=slope(Q[t-1],i)，都表示出现了可以删去点 \(Q[t]\) 的情况（只要对边界、去重的处理足够严谨，两种写法是没有区别的）。其中 \(Q\) 是维护凸包点集的队列。

该做法时间复杂度为 \(O(n\log n)\)，瓶颈在于二分寻找最优决策点。

三.【再优化】

运用决策单调性进行优化。决策单调性相关基础知识见 ，这里只放一下定义：
设 \(j_0[i]\) 表示 \(dp[i]\) 转移的最优决策点，那么决策单调性可描述为 \(\forall i\leqslant i',j_0[i]\leqslant j_0[i']\)。也就是说随着 \(i\) 的增大，所找到的最优决策点是递增态（非严格递增）。

(1).【决策单调性证明】

还是以 玩具装箱 为例，来简单证一波决策单调性，方法采用四边形不等式。

显然，本题的转移方程呈现出了 \(dp[i]=min(dp[j]+w(i,j))\) 的形式，即 \(1D/1D\) 动态规划方程，其中 \(w(i,j)=(S[i]?S[j]-1-L)^2\)。

\(证明：设\) \(Q=S[i]?S[j]-1-L\)

\(\therefore w(i,j)=(S[i]?S[j]-1-L)^2=Q^2\)

\(\begin{aligned} \therefore w(i+1,j+1)=&(S[i+1]?S[j+1]-1-L)^2\\ =&((S[i]+C[i+1]+1)?(S[j]+C[j+1]+1)-1-L)^2\\ =&(Q+C[i+1]-C[j+1])^2 \end{aligned}\)

\(\begin{aligned} w(i,j+1)=&(S[i]?S[j+1]-1-L)^2\\ =&(S[i]?(S[j]+C[j+1]+1)-1-L)^2\\ =&(Q-C[j+1]-1)^2 \end{aligned}\)

\(\begin{aligned} w(i+1,j)=&(S[i+1]?S[j]-1-L)^2\\ =&((S[i]+C[i+1]+1)?S[j]-1-L)^2\\ =&(Q+C[i+1]+1)^2 \end{aligned}\)

\(\therefore w(i,j)+w(i+1,j+1)=2Q^2+2C[i+1]Q-2C[j+1]Q+C[i+1]^2-2C[i+1]C[j+1]+C[j+1]^2\)

\(\therefore w(i+1,j)+w(i,j+1)=2Q^2+2C[i+1]Q-2C[j+1]Q+C[i+1]^2+2C[i+1]+2C[j+1]+C[j+1]^2+2\)

\(\therefore w(i,j)+w(i+1,j+1)-w(i+1,j)+w(i,j+1)=-2(C[i+1]+1)(C[j+1]+1)\)

\(又 \because C[i],C[j] \geqslant 1\)

\(\therefore -2(C[i+1]+1)(C[j+1]+1) \leqslant -8\)

\(\therefore w(i,j)+w(i+1,j+1) \leqslant w(i+1,j)+w(i,j+1)\)

四边形不等式成立，所以此方程具有决策单调性。
证毕。

(2).【单调队列】

由于最优决策点递增，可以用单调队列对其进行维护。操作 \((2),(3)\) 不需要改动，操作 \((1)\) 改为：判断当队首的第一根线段斜率小于等于 \(k_0[i]\) 时就出队，直至斜率大于 \(k_0[i]\)，此时的队首即为最优决策点。

正确性显然。因为随着 \(i\) 的变大，最优决策点 \(j_0[i]\) 也会跟着变大，如果已知某个点在当前情况下不够侑秀，那么在这之后也一定不会作为最优决策点，所以可以直接出队。

时间复杂度为 \(O(n)\) 。

(3).【再证决策单调性】

一样的，两种思路。

先观察 \(k_0[i]\) 的表达式：\(k_0[i]=2S[i]\) ，明显在本题中 \(k_0\) 呈单增态。

【代数法】

\(k_0[i]\) 递增就说明我们找到的第一个斜率大于 \(k_0[i]\) 的线段在不断地向后移，也就是说，如果我们找到了某一个最优决策点 \(j\)，那么在下一次决策中，最优决策点 \(j'\) 必定在 \(j\) 的后面。

决策单调性得证。

【线性规划】

画出草图：

直线 \(Line_i\) 的斜率 \(k_0[i]\) 递增，

由图可知最优决策点在递增。

决策单调性得证。

【其他】

从这个角度来看的话，貌似决策单调性和 \(X(j),k_0[i]\) 的单调性是相通的？

于是一个结论就出现了：如果 \(X(j),k_0[i]\) 均单调不减，则该方程必定有决策单调性（自己瞎 \(yy\) 的，不敢肯定一定正确）。

四.【Code】

【模板】 玩具装箱 \(toy\) \([P3195]\)

这道题 \(...\) 数据太水了 \(...\) 我一开始 \(\text{L}\) 忘了加 \(1\) 居然还过了 \(...\)

#include
#include
#define LL long long
#define Re register LL
const int N=5e4+5;
LL i,j,n,L,h=1,t=0,Q[N],S[N],dp[N];
//S[n]=∑C[i]+1, dp[i]=min(dp[j]+(S[i]-(S[j]+L+1))^2)，++L 
//dp[i]=S[i]^2-2*S[i]*L+dp[j]+(S[j]+L)^2-2S[i]*S[j]
//(2*S[i]) * S[j] + (dp[i]-S[i]^2+2S[i]L)=(dp[j]+(S[j]+L)^2)
//   k     *  x   +           b          =        y
inline LL min(Re a,Re b){return a=slope(Q[t-1],i))--t;//至少要有两个元素 h

#include
#define Re register int
const int N=4e6+105;
int i,j,n,m,h=1,t=0,T,ti,ans=2e9,G[N],S[N],Q[N],dp[N];
inline int min(Re a,Re b){return aY(i)?2e9:-2e9):(long double)(Y(j)-Y(i))/(long double)(X(j)-X(i));}
int main(){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;T=-min(-T,-ti),++G[ti],S[ti]+=ti,++i)scanf("%d",&ti);
    for(i=1;i=slope(Q[t-1],i-m+1))--t;
        Q[++t]=i-m+1;//(j+1)+m<=i
    }
    for(i=T;i

#include
#include
#define LL long long
#define Re register LL
const int N=1e4+5;
LL i,j,n,h=1,t=0,S,Q[N],ST[N],SF[N],dp[N];
//dp[p][i]=min(dp[p-1][j]+(ST[i]+S*p)*(SF[i]-SF[j]));
//dp[i]=dp[j]+ST[i]*(SF[i]-SF[j])+S*(SF[n]-SF[j]);
//(S+ST[i]) * SF[j] + (dp[i]-ST[i]*SF[i]-S*SF[i]) = (dp[j])
//    k     *   x   +              b              = y
inline LL min(Re a,Re b){return aslope(Q[t-1],i))--t;
        Q[++t]=i;
    }
    printf("%lld",dp[n]);
}

#include
#include
#define LL long long
#define Re register LL
const int N=3e5+5;
LL i,j,n,h=1,t=0,S,Q[N],ST[N],SF[N],dp[N];
//dp[p][i]=min(dp[p-1][j]+(ST[i]+S*p)*(SF[i]-SF[j]));
//dp[i]=dp[j]+ST[i]*(SF[i]-SF[j])+S*(SF[n]-SF[j]);
//(S+ST[i]) * SF[j] + (dp[i]-ST[i]*SF[i]-S*SF[i]) = (dp[j])
//    k     *   x   +              b              = y
//ti可小于0，所以ST[i]非递增，只可二分
//fi可等于0，所以SF[i](X)非严格递增，因此需要特判X(i)==X(j)的情况
inline LL min(Re a,Re b){return a=Y(i)?1e18:-1e18):(long double)(Y(j)-Y(i))/(X(j)-X(i));
}//由于需要二分查找，多了一些限制：队列里不能有在同一位置的点,返回inf还是-inf都影响着是否删除重点，平时不可不管，二分必须注意返回值
inline LL sakura(Re k){
    if(h==t)return Q[h];
    Re l=h,r=t;
    while(l>1,i=Q[mid],j=Q[mid+1];
        if(slope(i,j)Q[mid]s即j>i即SF[j]>SF[i]即X(j)>X(i)，如果是(i)-(j)的话乘过去要变号
        else r=mid;
    }
    return Q[l];
}
int main(){
    scanf("%lld%lld",&n,&S);
    for(i=1;i<=n;ST[i]+=ST[i-1],SF[i]+=SF[i-1],++i)scanf("%lld%lld",&ST[i],&SF[i]);
    Q[++t]=0;
    for(i=1;i<=n;++i){
        j=sakura(S+ST[i]);
        dp[i]=dp[j]+ST[i]*(SF[i]-SF[j])+S*(SF[n]-SF[j]);
        while(h=slope(Q[t-1],i))--t;//此处取等号作用出现，如果不取等，会WA第12个点
        Q[++t]=i;
    }
    printf("%lld",dp[n]);
}

#include
#include
#include
#define LD long double
#define LL long long
#define Re register int
#define S2(a) (1ll*(a)*(a))
using namespace std;
const LL N=1e5+3,inf=1e18;
int n,H[N],W[N],Q[N];LL S[N],dp[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
//dp[i]=min(dp[i],dp[j]+(H[i]-H[j])*(H[i]-H[j])+S[i-1]-S[j]);
//dp[i]=dp[j]-2*H[i]*H[j]+H[j]*H[j]+H[i]*H[i]+S[i-1]-S[j]
//(2*H[i]) * H[j] + (dp[i]-S[i-1]-H[i]*H[i]) = (dp[j]+H[j]*H[j]-S[j])
//   k     *  x   +            b             =          y
#define X(j) (a[j].x)
#define Y(j) (a[j].y)
struct QAQ{
    int k,x,id;LL y;
    inline bool operator<(const QAQ &O)const{return x!=O.x?xY(i)?inf:-inf):(LD)(Y(j)-Y(i))/(X(j)-X(i));}
inline void CDQ(Re L,Re R){
    if(L==R){Re j=a[L].id;a[L].y=dp[j]+(LL)H[j]*H[j]-S[j];return;}//此时dp[j]必定已经求出来了，直接算计Y(j)即可
    Re mid=L+R>>1,p1=L,p2=mid+1,h=1,t=0;
    for(Re i=L;i<=R;++i)a[i].id<=mid?b[p1++]=a[i]:b[p2++]=a[i];//按照i的大小分到左右两边（两边的k0[i]分别递增）
    for(Re i=L;i<=R;++i)a[i]=b[i];
    CDQ(L,mid);//处理完左边后，左边的X(j)是递增的，此时右边还没处理，所以右边k0[i]是递增的
    for(Re i=L;i<=mid;++i){//把左边的点拿出来维护凸包（使用单调队列）
        while(h=slope(Q[t-1],i))--t;
        Q[++t]=i;
    }
    for(Re i=mid+1,j,id;i<=R;++i){//把右边的点拿来决策（依旧是单调队列）
        while(h