Print Article(hdu - 3507)之浅谈如何用斜率优化巧解DP

太过爱你忘了你带给我的痛 2022-03-26 03:22 205阅读 0赞

**目录**

前言

斜率优化

一般常见方程

题目

斜率优化之推理

斜率优化之下凸包

斜率优化之凸包判断

斜率优化之参考代码

后记

--------------------

# 前言 #

以前我们已经学习过了几种DP优化，例如**平行四边形不等式优化DP**和**单调队列或单调栈优化DP**。因此，我们也对dp似乎有了一定了解。但是光这两种好像还是不太够，因此今天将引入一种全新的 十分牛逼 的优化方法 —— **斜率优化**。

不知道大家在听到这个很厉害的名字的时候心中有没有一震，记得不久前本校da lao在考完NOIP普及后说过好像第三题得用斜率优化，当时就震惊了（当然最后也不需要用到哈）。这让大家望而生畏是有一定道理的，毕竟它涉及到了许多数学知识：例如计算直线的斜率；通过叉积判断直线上凸还是下凸（会的可跳过哈，别嘲笑人家）……

但是呢这些东西看上去很难，其实也不是特别 *抽象* ，只要学懂了还是能看懂其中的一套一套的。所以我们今天就是来粗略的根据一道比较典型的题目——Print Article来解析一下斜率优化。

# 斜率优化 #

## 一般常见方程 ##

在做题中肯定比较常见这种方程：![dp\[i\] = min \\left \\\{ dp\[j\] + \\left | w\[i\] - w\[j\] \\right | \\right \\\}][dp_i_ _ min _left _ dp_j_ _ _left _ w_i_ - w_j_ _right _ _right]，这样的方程可以通过**去绝对值**来得到**只跟j有关**的转移，然后通过**单调队列优化**求解即可。又或者说还有这种方程：![dp\[i\]\[j\] = min \\left \\\{dp\[k\]\[j - 1\] + w (k + 1, i) \\right \\\}][dp_i_j_ _ min _left _dp_k_j - 1_ _ w _k _ 1_ i_ _right]，这也是可以通过演算看出来是一个**四边形不等式优化**的转移方程。

但如果说是这种呢？![dp\[i\] = min \\left \\\{ dp\[j\] + (sum\[i\] - sum\[j\])^\{2\} \\right \\\}][dp_i_ _ min _left _ dp_j_ _ _sum_i_ - sum_j_2_ _right]有些人或许会想到化简，那我们就化一下吧。![dp\[i\] = min \\left \\\{ dp\[j\] + sum\[i\] ^\{2\} + sum\[j\]^\{2\} - 2 \* sum\[i\] \* sum\[j\] \\right \\\}][dp_i_ _ min _left _ dp_j_ _ sum_i_ _2_ _ sum_j_2_ - 2 _ sum_i_ _ sum_j_ _right]在这里可以把sum\[i\] ^ 2提出来，可是这中间还有一个2 \* sum\[i\] \* sum\[j\]呀，这里面不能再分解为一个**只跟i或只跟j有关**的式子了。那么这个时候，就需要传说中的 ***斜率优化*** 来登场了！

## 题目 ##

Zero has an old printer that doesn't work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero use a cost to evaluate this degree.   
One day Zero want to print an article which has N words, and each word i has a cost Ci to be printed. Also, Zero know that print k words in one line will cost

M is a const number.

Now Zero want to know the minimum cost in order to arrange the article perfectly.

**输入**

There are many test cases. For each test case, There are two numbers N and M in the first line (0 ≤ n ≤ 500000, 0 ≤ M ≤ 1000). Then, there are N numbers in the next 2 to N + 1 lines. Input are terminated by EOF.

**输出**

A single number, meaning the mininum cost to print the article.

**样例输入**

5 5
    5
    9
    5
    7
    5

**样例输出**

230

大意就是说有n个单词，每个单词有相关的花费，打印连续k个单词会花费**这些花费总和的平方加上M**，请问打印所有的单词的最小花费。

可以很容易的拿出转移方程吧：![dp\[i\] = min \\left \\\{ dp\[j\] + (sum\[i\] - sum\[j\])^\{2\} \\right \\\} + M][dp_i_ _ min _left _ dp_j_ _ _sum_i_ - sum_j_2_ _right _ _ M]。（sum代表着前缀和）

这个意思也就是说从1 ~ i - 1来推最优决策点j，使得这个转移方程花费最小。当然，我们可以在草稿纸上化简（或者叫做推理）一下。

## 斜率优化之推理 ##

我们可以假设有两个决策点：j 和 k，那么如果说j要优于k的话，也就是说j相关方程会优于k相关方程。![dp\[j\] + (sum\[i\] - sum\[j\])^\{2\} + M < dp\[k\] + (sum\[i\] - sum\[k\])^\{2\}][dp_j_ _ _sum_i_ - sum_j_2_ _ M _ dp_k_ _ _sum_i_ - sum_k_2]。

把括号拆开，再化一下简，就会变成这样：![dp\[j\] + sum\[j\] ^\{2\} - 2 \* sum\[i\] \* sum\[j\] < dp\[k\] + sum\[k\] ^\{2\} - 2 \* sum\[i\] \* sum\[k\]][dp_j_ _ sum_j_ _2_ - 2 _ sum_i_ _ sum_j_ _ dp_k_ _ sum_k_ _2_ - 2 _ sum_i_ _ sum_k]。

再移一下项，那么就会变成：![dp\[j\] + sum\[j\] ^\{2\} - dp\[k\] - sum\[k\] ^\{2\} < 2 \* sum\[i\] \* (sum\[j\] - sum\[k\])][dp_j_ _ sum_j_ _2_ - dp_k_ - sum_k_ _2_ _ 2 _ sum_i_ _ _sum_j_ - sum_k]。

又因为sum是前缀和，如果说j > k,那么sum\[j\] 就会大于sum\[k\]，即可得到![\\frac\{dp\[j\] + sum\[j\] ^\{2\} - dp\[k\] - sum\[k\] ^\{2\}\}\{2 \* (sum\[j\] - sum\[k\])\} < sum\[i\]][frac_dp_j_ _ sum_j_ _2_ - dp_k_ - sum_k_ _2_2 _ _sum_j_ - sum_k_ _ sum_i]；

可如果说是小于，那么就变成了这种：![\\frac\{dp\[j\] + sum\[j\] ^\{2\} - dp\[k\] - sum\[k\] ^\{2\}\}\{2 \* (sum\[j\] - sum\[k\])\} > sum\[i\]][frac_dp_j_ _ sum_j_ _2_ - dp_k_ - sum_k_ _2_2 _ _sum_j_ - sum_k_ _ sum_i 1]。

在这里，我们把**dp\[j\] + sum\[j\] ^ 2设为Yj，2 \* sum\[j\]设为Xj，**那么就可以得到![\\frac\{Yj - Yk\}\{Xj - Xk\} >(<) sum\[i\]][frac_Yj - Yk_Xj - Xk_ _ sum_i]，乍一眼看，**这不就是直线的斜率表示**吗？

因此我们就得到了第一个结论：

> 感性理解就是两个决策点的斜率如果小于了sum\[i\]，那么靠后的决策点就会更优，否则就是前面的更优。

这个大家可以再理解理解（当时我也想了一会，但是好好看了这个条件后就能看出来了。如果说没看懂的话可以再下去想想 明天再来看也许就看懂了也说不定 ）

当然，通过这个东西，我们也就可以借助单调队列来进一步优化了。

### 斜率优化之下凸包 ###

尽管上面的结论看上去似乎已经很厉害了，但是这对于斜率优化来说还是远远不够的。接下来还会对斜率优化有一个进一步的分析。

如果我们令**函数g为斜率**，也就是说g (i, j)代表着直线ij的斜率。那么假设有三个决策点：i，j，k且k < j < i，同时g (i, j) < g (j, k)（如图）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70][]

那么在这里，sum\[a\]是有三种取值情况的：**①sum\[a\] > g (i, j) 并且 sum\[a\] > g (j, k)。②sum\[a\] > g (i, j) 但是 sum\[a\] < g (j, k)。③sum\[a\] < g (i, j) 并且 sum\[a\] < g (j, k)。**在这里，我们就一一来讨论一下吧。

**①**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 1][]

在这里套用上面的第一个结论可以得到，在直线jk中，因为g (j, k) < sum\[a\]，那么k肯定是要优于j的。而在直线ij中j又要优于i一些。相较之下，可以得到k是最优的。

**②**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 2][]

在这里呢，因为g (i, j) < sum\[a\]，那么i会优于j一些，可是g (j, k) > sum\[a\]，那么k又要优于j，因此j也不是最优的。

**③**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 3][]

而在这里呢，两个都小于了sum\[a\]，那么最后面的一定要更优一些，因此i是最优的。j还不是最优……

所以呢，从上面三种情况可以得知：

> 所有的决策点连线后，会满足一个下凸包性质。

当然，这就是我们关于斜率优化的第二个 ***牛逼*** 的结论了。

所谓下凸包其实很形象，就是一个往下凸的一个几何图形罢了 （大家可以跳过这句没用的话），反正我当时就是这么理解的。如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 4][]

可以由图像中可知，每个最佳决策点所连成的直线斜率是满足一个单调上升的趋势的，那么就可以用上 **单调队列** 来优化了吧。

因此现在就能够将这道题的大致斜率优化思路拿出来了呢：

> 于是对于这题我们对于斜率优化做法可以总结如下：
> 
> 1，用一个**单调队列来维护解集**。
> 
> 2，假设队列中从头到尾已经有元素a b c。那么当d要入队的时候，我们**维护队列的下凸性质**，即如果g\[d,c\]<g\[c,b\]，那么就将**c点删除。直到找到****g\[d,x\]>=g\[x,y\]****为止，并将d点加入在该位置中**。
> 
> 3，找最佳决策点时，设当前求解状态为i，从队头开始，如果已有元素a b c，当i点要求解时，**如果g\[b,a\]<sum\[i\]，那么说明****b点比a点更优****，a点可以排除，于是a出队，直到****第一次遇到g\[j,j-1\]>sum\[i\]****，此时j-1即为最佳决策点**。

### 斜率优化之凸包判断 ###

那么如果说有三个点i, j, k，其中Xi < Xj < Xk，那么应该怎么判断这三个点连成的线是上凸还是下凸呢？在这里将引入一个新的几何知识——向量叉积。（会这方面知识的da lao们可以跳过了）

在这里因为深感数学+几何的重要性（并不是说语文英语这些就不重要了哈），已经感觉到了深深地无力感（因此有哪些学过这方面知识的dalao可以评论指出我的不足，感激不尽）。话接上文，因为知识并没有到位，所以不能给大家一些错误的东西，因此 ***被迫***  不得不粘一些权威的学术语言来充实一下了。（以下都是重点！！！！！）

> 向量可以看做是二维平面坐标中的**有向线段**。向量的起点可以**自由选择**，即可以把它在平面内任意平移。平移过后的向量与原平移前**完全等价**。如果一条有向线段的起点为(x1,y1),终点为(x2,y2)。我们可以将它平移，**使得起点位置为(0,0),终点位置为(x2-x1,y2-y1)**。此时向量的大小和方向不变。我们以后谈及向量，**都默认它的起点在(0,0)处，而只以它的终点表示该向量**。
> 
> 设有向量p1(x1,y1)，p2(x2,y2)。他们的叉乘为p1*×*p2=(x1\*y2-x2\*y1)。
> 
> **叉乘的物理意义为以向量p1和p2为相邻两边的平行四边形的有向面积**。
> 
> 左图为正向有向面积，右图为负向有向面积。
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 5][]
> 
> 平面四边形在两向量的顺时针方向，则为正，反之则为负。如何判断p1与p2的位置关系？
> 
> **若p1*×*p2>0，则p2在p1的逆时针方向；**
> 
> **若p1*×*p2<0，则p2在p1的顺时针方向；**
> 
> **若p1*×*p2=0，则p1与p2方向重合。**
> 
> 所以我们可以令向量p1=(xj-xk,yj-yk),p2=(xi-xj,yj-yk)，再用**叉积即可判断i，j，k是上凸还是下凸**。
> 
> **同时由于精度问题，所以我们尽量用乘法代替除法来比较斜率。**

当然如果说还一知半解或不太满意的朋友可以自己百度一下（原谅我的无知）

### 斜率优化之参考代码 ###

#include <cstdio>
    #include <cstring>
    using namespace std;
    #define N 500000
    
    void read (int &x){
        x = 0;
        char c = getchar ();
        while (c < '0' || c > '9')
            c = getchar ();
        while (c >= '0' && c <= '9'){
            x = (x << 1) + (x << 3) + c - 48;
            c = getchar ();
        }
    }
    
    void print (int x){
        if (x / 10)
            print (x / 10);
        putchar (x % 10 + 48);
    }
    
    int n, m, cost[N + 5], dp[N + 5], sum[N + 5];
    int q[N + 5], head, tail;
    
    int UP (int i, int j){//求分母部分，也就是Yi - Yj
        return dp[i] + sum[i] * sum[i] - dp[j] - sum[j] * sum[j];
    }
    
    int DOWN (int i, int j){//求分子，也就是2 * (Xi - Xj)
        return (sum[i] - sum[j]) * 2;
    }
    
    int main (){
        while (~ scanf ("%d%d", &n, &m)){
            memset (dp, 0, sizeof (dp));
            memset (sum, 0, sizeof (sum));
            memset (q, 0, sizeof (q));
            for (int i = 1; i <= n; i++)
                read (cost[i]);
            for (int i = 1; i <= n; i++)//求前缀和
                sum[i] = sum[i - 1] + cost[i];
            head = tail = 0;//手动模拟单调队列
            tail ++;//这里是要初始化队列
            for (int i = 1; i <= n; i++){
                //在这里为什么要head + 1 < tail呢？是因为要保证队列中至少要有三个元素才能够求向量叉积
                //后面的部分就是把那个叉积计算变成了乘法而已，大家可以自己推一推
                while (head + 1 < tail && UP(q[head + 1], q[head]) <= sum[i] * DOWN (q[head + 1], q[head]))
                    head ++;
                dp[i] = dp[q[head]] + (sum[i] - sum[q[head]]) * (sum[i] - sum[q[head]]) + m;//dp转移
                while (head + 1 < tail && DOWN (q[tail - 1], q[tail - 2]) * UP (i, q[tail - 1]) <= UP (q[tail - 1], q[tail - 2]) * DOWN (i, q[tail - 1]))
                    tail --;//将后面不满足的部分全部都踢掉，将dp[i]放在合适的位置
                q[tail++] = i;
            }
            print (dp[n]);
            putchar (10);
        }
    }

# 后记 #

斜率优化毕竟是个很难的知识，大家有些没看懂也是正常的，毕竟在码这篇博客时我都也只是刚刚才差不多把这道题搞懂，大家可以下去再想想，或者说用草稿本算一算画一画，或者第二天再来看几次，再好好理解理解，总能搞懂的。

当然，在码这篇博客时，我自己也有了一些新的体会，同时也要感谢wyw帮助我入门，不然还会在门槛那里再卡着。

同时呢对于上文的一些错误也欢迎，希望大家指出来，在我没讲懂的一些东西时大家也希望能够多包容，毕竟我也还有很多瑕疵嘛，大家一起进步咯！

[dp_i_ _ min _left _ dp_j_ _ _left _ w_i_ - w_j_ _right _ _right]: https://private.codecogs.com/gif.latex?dp%5Bi%5D%20%3D%20min%20%5Cleft%20%5C%7B%20dp%5Bj%5D%20&plus;%20%5Cleft%20%7C%20w%5Bi%5D%20-%20w%5Bj%5D%20%5Cright%20%7C%20%5Cright%20%5C%7D
[dp_i_j_ _ min _left _dp_k_j - 1_ _ w _k _ 1_ i_ _right]: https://private.codecogs.com/gif.latex?dp%5Bi%5D%5Bj%5D%20%3D%20min%20%5Cleft%20%5C%7Bdp%5Bk%5D%5Bj%20-%201%5D%20&plus;%20w%20%28k%20&plus;%201%2C%20i%29%20%5Cright%20%5C%7D
[dp_i_ _ min _left _ dp_j_ _ _sum_i_ - sum_j_2_ _right]: https://private.codecogs.com/gif.latex?dp%5Bi%5D%20%3D%20min%20%5Cleft%20%5C%7B%20dp%5Bj%5D%20&plus;%20%28sum%5Bi%5D%20-%20sum%5Bj%5D%29%5E%7B2%7D%20%5Cright%20%5C%7D
[dp_i_ _ min _left _ dp_j_ _ sum_i_ _2_ _ sum_j_2_ - 2 _ sum_i_ _ sum_j_ _right]: https://private.codecogs.com/gif.latex?dp%5Bi%5D%20%3D%20min%20%5Cleft%20%5C%7B%20dp%5Bj%5D%20&plus;%20sum%5Bi%5D%20%5E%7B2%7D%20&plus;%20sum%5Bj%5D%5E%7B2%7D%20-%202%20*%20sum%5Bi%5D%20*%20sum%5Bj%5D%20%5Cright%20%5C%7D
[dp_i_ _ min _left _ dp_j_ _ _sum_i_ - sum_j_2_ _right _ _ M]: https://private.codecogs.com/gif.latex?dp%5Bi%5D%20%3D%20min%20%5Cleft%20%5C%7B%20dp%5Bj%5D%20&plus;%20%28sum%5Bi%5D%20-%20sum%5Bj%5D%29%5E%7B2%7D%20%5Cright%20%5C%7D%20&plus;%20M
[dp_j_ _ _sum_i_ - sum_j_2_ _ M _ dp_k_ _ _sum_i_ - sum_k_2]: https://private.codecogs.com/gif.latex?dp%5Bj%5D%20&plus;%20%28sum%5Bi%5D%20-%20sum%5Bj%5D%29%5E%7B2%7D%20&plus;%20M%20%3C%20dp%5Bk%5D%20&plus;%20%28sum%5Bi%5D%20-%20sum%5Bk%5D%29%5E%7B2%7D
[dp_j_ _ sum_j_ _2_ - 2 _ sum_i_ _ sum_j_ _ dp_k_ _ sum_k_ _2_ - 2 _ sum_i_ _ sum_k]: https://private.codecogs.com/gif.latex?dp%5Bj%5D%20&plus;%20sum%5Bj%5D%20%5E%7B2%7D%20-%202%20*%20sum%5Bi%5D%20*%20sum%5Bj%5D%20%3C%20dp%5Bk%5D%20&plus;%20sum%5Bk%5D%20%5E%7B2%7D%20-%202%20*%20sum%5Bi%5D%20*%20sum%5Bk%5D
[dp_j_ _ sum_j_ _2_ - dp_k_ - sum_k_ _2_ _ 2 _ sum_i_ _ _sum_j_ - sum_k]: https://private.codecogs.com/gif.latex?dp%5Bj%5D%20&plus;%20sum%5Bj%5D%20%5E%7B2%7D%20-%20dp%5Bk%5D%20-%20sum%5Bk%5D%20%5E%7B2%7D%20%3C%202%20*%20sum%5Bi%5D%20*%20%28sum%5Bj%5D%20-%20sum%5Bk%5D%29
[frac_dp_j_ _ sum_j_ _2_ - dp_k_ - sum_k_ _2_2 _ _sum_j_ - sum_k_ _ sum_i]: https://private.codecogs.com/gif.latex?%5Cfrac%7Bdp%5Bj%5D%20&plus;%20sum%5Bj%5D%20%5E%7B2%7D%20-%20dp%5Bk%5D%20-%20sum%5Bk%5D%20%5E%7B2%7D%7D%7B2%20*%20%28sum%5Bj%5D%20-%20sum%5Bk%5D%29%7D%20%3C%20sum%5Bi%5D
[frac_dp_j_ _ sum_j_ _2_ - dp_k_ - sum_k_ _2_2 _ _sum_j_ - sum_k_ _ sum_i 1]: https://private.codecogs.com/gif.latex?%5Cfrac%7Bdp%5Bj%5D%20&plus;%20sum%5Bj%5D%20%5E%7B2%7D%20-%20dp%5Bk%5D%20-%20sum%5Bk%5D%20%5E%7B2%7D%7D%7B2%20*%20%28sum%5Bj%5D%20-%20sum%5Bk%5D%29%7D%20%3E%20sum%5Bi%5D
[frac_Yj - Yk_Xj - Xk_ _ sum_i]: https://private.codecogs.com/gif.latex?%5Cfrac%7BYj%20-%20Yk%7D%7BXj%20-%20Xk%7D%20%3E%28%3C%29%20sum%5Bi%5D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70]: /images/20220326/72778018f2754a8182a3ebfb2236f190.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 1]: /images/20220326/79332b26fd9040b4b524f4404c77e8c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 2]: /images/20220326/6e89c1a36f5d4cefbdaa84c742718e81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 3]: /images/20220326/d562c6f231c548aaa17e2586e325ba26.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 4]: /images/20220326/10882ed6e92846fc98cf51fdff692006.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 5]: /images/20220326/16882e4e918748028f8b3bf5968ad821.png