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

辰星凌 · 2019-07-19 08:28:46 · 题解

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

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<j_2<i) 为 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] \text{又} \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<j_2<i)，使得不等式 \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]，由上述结论可知：

$(b).$ 若 $k_2 \leqslant k_0$，则 $j_3$ 优于 $j_2$ 。反之，若 $k_2 > k_0$，则 $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} 方程可化为：

其中 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。

其实也可以化为：

其中 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')} 的形式，需要通过一系列代数推导后再绘草图模拟决策。

二.【维护凸包】

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

用单调队列维护凸包点集，操作分三步走：

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

(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 呈单增态。

【代数法】

#include<cstring>
#include<cstdio>
#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<b?a:b;}
inline LL X(Re j){return S[j];}
inline LL Y(Re j){return dp[j]+(S[j]+L)*(S[j]+L);}
inline long double slope(Re i,Re j){return (long double)(Y(j)-Y(i))/(X(j)-X(i));}//记得开long double 
int main(){
    scanf("%lld%lld",&n,&L);++L; 
    for(i=1;i<=n;S[i]+=S[i-1]+1,++i)scanf("%lld",&S[i]);
    Q[++t]=0;//重中之重 
    for(i=1;i<=n;++i){
        while(h<t&&slope(Q[h],Q[h+1])<=2*S[i])++h;//至少要有两个元素 h<t。出队判断时尽量加上等号 
        dp[i]=dp[j=Q[h]]+(S[i]-S[j]-L)*(S[i]-S[j]-L);
        while(h<t&&slope(Q[t-1],Q[t])>=slope(Q[t-1],i))--t;//至少要有两个元素 h<t。入队判断时尽量加上等号 
        Q[++t]=i;
    }
    printf("%lld",dp[n]);
}

五.【各种玄学问题】

(ノ°ο°)ノ前方高能预警 (＊°ω°＊)ノ"非战斗人员请撤离!! ＊・_・)ノ

(1).【T1】

设 ST[i]=\sum_{j=1}^i T[j],SF[i]=\sum_{j=1}^i F[j]

压成了 O(n^2) 后，T1 就可以 \text{AC} 了，但它还能继续优化。

(2).【T2】

先转化为斜率式看看？

其中 k=S+ST[i], x=SF[j], b=dp[i]-ST[i]\times SF[i]-S\times SF[i], y=dp[j] 。

决策点要使得 dp[i] 尽量小，且 S+ST[i] 和 SF[j] 都严格单增，所以直接用单调队列维护一个下凸包即可。

时间复杂度为 O(n) 。

【Code】

#include<cstring>
#include<cstdio>
#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 a<b?a:b;}
inline LL X(Re j){return SF[j];}
inline LL Y(Re j){return dp[j];}
inline long double slope(Re i,Re j){return (long double)(Y(j)-Y(i))/(X(j)-X(i));}
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){
        while(h<t&&slope(Q[h],Q[h+1])<(S+ST[i]))++h;
        dp[i]=dp[j=Q[h]]+ST[i]*(SF[i]-SF[j])+S*(SF[n]-SF[j]);
        while(h<t&&slope(Q[t-1],Q[t])>slope(Q[t-1],i))--t;
        Q[++t]=i;
    }
    printf("%lld",dp[n]);
}

(3).【T3】

因 F_i 可等于 0，X(j) ( 即 SF[i]) 非严格递增，所以需要特判 X(j_1)=X(j_2) 的情况（但仍具有单调性，可以使用队列维护凸包）。

因 T_i 可小于 0，k_0[i]( 即 S+ST[i]) 无单调性，所以不具有决策单调性，可以用四边形不等式进行证明：

该 \text{dp} 方程显然为 dp[i]=dp[j]+w(i,j) 的形式，其中 w(i,j)=ST[i](SF[i]-SF[j])+S(SF[n]-SF[j]) 。

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

此时需要在队列中二分查找最优决策点。

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

【Code】

#include<cstring>
#include<cstdio>
#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<b?a:b;}
inline LL X(Re j){return SF[j];}
inline LL Y(Re j){return dp[j];}
inline long double slope(Re i,Re j){return X(j)==X(i)?(Y(j)>=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<r){
        Re mid=l+r>>1,i=Q[mid],j=Q[mid+1];
        if(slope(i,j)<k)l=mid+1;
//      if( (Y(j) - Y(i)) < k * (X(j) - X(i)) )l=mid+1;//注意是(j)-(i)因为Q[mid+1]>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<t&&slope(Q[t-1],Q[t])>=slope(Q[t-1],i))--t;//此处取等号作用出现，如果不取等，会WA第12个点
        Q[++t]=i;
    }
    printf("%lld",dp[n]);
}

3.【CDQ/平衡树】

因为暂时没找到 X(j) 不单调、k_0[i] 单调的例题，这里直接讲两者均不单调的情况。

• \text{Building Bridges [CEOI2017] [P4655]}

如果学习了动态凸包算法，会发现这其实就是套了个板子上去（平衡树代码较毒瘤就不放了）。