DP优化（二）斜率优化实例讲解

有一类DP状态方程，例如：

dp[i]=min{dp[j]−a[i]∗d[j]}  0≤j<i,d[j]≤d[j+1],a[i]≤a[i+1]

它的特征是存在一个既有 i 又有 j 的项 a[i]∗d[j] 。编程时，如果简单地对 i 和 j 循环，复杂度是 O(n2) 的。通过斜率优化（凸壳优化），把时间复杂度优化到 O(n)。

斜率优化的核心技术是斜率（凸壳）模型和单调队列。

一、把状态方程变换为平面的斜率问题

方程对某个固定的 i，求 j 变化时 dp[i] 的最优值，所以可以把关于 i 的部分看成固定值，把关于 j 的部分看成变量。把 min 去掉，方程转化为：dp[j]=a[i]∗d[j]+dp[i]

为方便观察，令：y=dp[j]，x=d[j]，k=a[i]，b=dp[i]，方程变为：y=kx+b

斜率优化的数学模型，就是把状态转移方程转换为平面坐标系直线的形式：y=kx+b。其中：

（1）变量 x 、y 和j 有关，并且只有 y 中包含 dp[j] 。点 (x,y) 是题目中可能的决策。

（2）斜率 k 、截距 b 与 i 关，并且只有 b 中包含 dp[i] 。最小的 b 包含最小的 dp[i]，也就是状态方程的解。

注意应用斜率优化的2个条件：x 和 k 是单调增加的，即 x 随着 j 递增而递增，k 随着 i 递增而递增。

二、求一个dp[i]

先考虑固定 i 的情况下求 dp[i] 。由于 i 是定值，那么斜率 k=a[i] 可以看成常数。当 j 在 0≤j<i 内变化时，对某个，产生一个点，这个点在一条直线上，是截距。如图1。

图1 经过点(x, y)的直线

对于 0≤j<i 中所有的 j ，把它们对应的点都画在平面上，这些点对应的直线的斜率 k=a[i] 都相同，只有截距 b 不同。在所有这些点中，有一个点 v ′ 所在的直线有最小截距 b ′ ，算出 b ′ ，由于 b ′ 中包含 dp[i]，那么就算出了最优的 dp[i]。如图。

图2 经过最优点v'的直线

如何找最优点v′？利用“下凸壳”。

前面提到，x 是单调增加的，即 x 随着 j 递增而递增。下图中给出了4个点，它们的 x 坐标是递增的。

图3 用下凸壳找最优点

图3(1)中的1、2、3构成了“下凸壳”，“下凸壳”的特征是线段12的斜率小于线段23的斜率。2、3、4构成了“上凸壳”。经过上凸壳中间点3的直线，其截距b肯定小于经过2或4的有相同斜率的直线的截距，所以点3肯定不是最优点，去掉它。

去掉“上凸壳”后，得到图3(2)，留下的点都满足“下凸壳”关系。最优点就在“下凸壳”上。例如在图3(3)中，用斜率为k kk的直线来切这些点，设线段12的斜率小于k ，24的斜率大于k ，那么点2就是“下凸壳”的最优点。

以上操作用单调队列编程很方便。

（1）进队操作，在队列内维护一个“下凸壳”，即每2个连续点组成的直线，其斜率是单调上升的。新的点进队列时，确保它能与队列中的点一起仍然能够组成“下凸壳”。例如队列尾部的2个点是v1、v2，准备加入队列的新的点是v3。比较v1、v2、v3，看线段v1v2和v2v3的斜率是否递增，如果是，那么v1、v2、v3形成了“下凸壳”；如果斜率不递增，说明v2不对，从队尾弹走它；然后继续比较队列尾部的2个点和v3；重复以上操作，直到v3能进队为止。经过以上操作，队列内的点组成了一个大的“下凸壳”，每2个点组成的直线，斜率递增，队列保持为单调队列。

（2）出队列，找到最优点。设队头的2个点是v1、v2，如果线段v1v2的斜率比k 小，说明v1不是最优点，弹走它，继续比较队头新的2个点，一直到斜率大于k 为止，此时队头的点就是最优点v ′ 。

三、求所有的dp[i]

以上求得了一个 dp[i]，复杂度 O(n)。如果对所有的 i ，每一个都这样求 p[i]，总复杂度仍然是 O(n2) 的，并没有改变计算的复杂度。有优化的方法吗？

一个较小的i1，它对应的点是 {v0,v1,...,vi1}；一个较大的 i2，对应了更多的点 {v0,v1,...,vi1,...,vi2}，其中包含了 i1 的所有点。当寻找i1的最优点时，需要检查 {0,v1,...,vi1}；寻找 i2 的最优点时，需要检查 {v0,v1,...,vi1,...,vi2}。这里做了重复的检查，并且这些重复是可以避免的。这就是能优化的地方，仍然用“下凸壳”进行优化。

（1）每一个 i 所对应的斜率 ki=a[i] 是不同的，根据约束条件 a[i]≤a[i+1]，当 i 增大时，斜率递增。

图4 多个 i 对应的直线

（2）前面已经提到，对一个i1找它的最优点的时候，可以去掉一些点，即那些斜率比ki1小的点。这些被去掉的点，在后面更大的i2时，由于斜率ki2也更大，肯定也要被去掉。

根据（1）和（2）的讨论，优化方法是：对所有的 i ，统一用一个单调队列处理所有的点；被较小的 i1 去掉的点，被单调队列弹走，后面更大的 i2 不再处理它们。

因为每个点只进入一次单调队列，总复杂度 O(n)。

下面的代码演示了以上操作。

//q[]是单调队列，head指向队首，tail指向队尾，slope()计算2个点组成的直线的斜率
for(int i=1;i<=n;i++){
    while(head<tail && slope(q[head],q[head+1])<k) //队头的2个点斜率小于k
        head++; //不合格，从队头弹出
    int j = q[head]; //队头是最优点
    dp[i] = ...; //计算dp[i]
    while(head<tail && slope(i,q[tail-1])<slope(q[tail-1],q[tail])) //进队操作
        tail--; //弹走队尾不合格的点
    q[++tail] = i; //新的点进队列
}

为加深对上述代码的理解，考虑一个特例：进入队列的点都符合“下凸壳”特征，且这些点组成的直线的斜率大于所有的斜率 ki，那么结果是：队头不会被弹出，进队的点也不会被弹出，队头被重复使用 n 次。

图5 一个特例

四、例题

下面用一个例题给出典型代码。

题目描述：打印一篇包含 N 个单词的文章，第i个单词的打印成本为 Ci。在一行中打印k个单词的花费是 ，M 是一个常数。如何安排文章，才能最小化费用？

输入：有很多测试用例。对于每个测试用例，第一行中都有两个数字 N 和 M（0≤n≤500000，0≤M≤1000）。然后，在接下来的2到 N + 1 行中有 N 个数字。输入用 EOF 终止。

输出：一个数字，表示打印文章的最低费用。

样例输入：

5 5

5

9

5

7

5

样例输出：

230

题目的意思是：有 N 个数和一个常数 M ，把这 N 个数分成若干部分，每一部分的计算值为这部分数的和的平方加上 M ，总计算值为各部分计算值之和，求最小的总计算值。由于 N 很大，O(N2) 的算法超时。

设dp[i]表示输出前i 个单词的最小费用，DP转移方程：

dp[i]=min{dp[j]+(sum[i]−sum[j])2+M}   0<j<i

其中 sum[i] 表示前 i 个数字和。

下面把DP方程改写为 y=kx+b 的形式。首先展开方程：dp[j]+sum[i]∗sum[i]+sum[j]∗sum[j]−2∗sum[i]∗sum[j]+M

移项得：dp[j]+sum[j]∗sum[j]=2∗sum[i]∗sum[j]+dp[i]−sum[i]∗sum[i]−M

对照 y=kx+b，有：y=dp[j]+sum[j]∗sum[j]，y 只和 j 有关。

x=2∗sum[j]，x 只和 j 有关，且随着 j 递增而递增。

k=sum[i]，k 只和 j 有关，且随着 i 递增而递增。

b=dp[i]−sum[i]∗sum[i]−M，b 只和 i 有关，且包含 dp[i]。

下面给出代码。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500010;

int dp[MAXN];
int q[MAXN]; //单调队列
int sum[MAXN];

int X(int x){ return 2*sum[x]; }
int Y(int x){ return dp[x]+sum[x]*sum[x]; }
//double slope(int a,int b){return (Y(a)-Y(b))/(X(a)-X(b));} //除法不好，改成下面的乘法
int slope_up  (int a,int b) { return Y(a)-Y(b);} //斜率的分子部分
int slope_down(int a,int b) { return X(a)-X(b);} //斜率的分母部分

int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;i++) scanf("%d",&sum[i]);
        sum[0] = dp[0] = 0;
        for(int i=1;i<=n;i++) sum[i]+=sum[i-1];

        int head=1,tail=1; //队头队尾
        q[tail]=0;
        for(int i=1;i<=n;i++){
            while(head<tail &&
                  slope_up(q[head+1],q[head])<=sum[i]*slope_down(q[head+1],q[head]))
               head++; //斜率小于k，从队头弹走

            int j = q[head]; //队头是最优点
            dp[i] = dp[j]+m+(sum[i]-sum[j])*(sum[i]-sum[j]); //计算dp[i]

            while(head<tail &&
                              slope_up(i,q[tail])*slope_down(q[tail],q[tail-1])
                           <= slope_up(q[tail],q[tail-1])*slope_down(i,q[tail]))
                tail--; //弹走队尾不合格的点
            q[++tail] = i; //新的点进队尾
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}