浅谈斜率优化

有一类问题，将n个物品分为连续的若干份（不限制份数），每分一次会产生一个代价（告诉你代价的计算方式），问代价最大/最小是多少。

容易想到，可以用线性DP来解决该问题。令f[i]表示选择前i个物品的最大/最小代价，则f[i]=min{f[j]+转移代价}(1<=j<i)。

朴素算法的复杂度为O(n^2)

根据具体问题，我们来研究如何优化这一算法。

一、转移代价为该段物品的价格之和

具体地，序列里的每样物品有一个价值值a[i]，我们用sum[i]表示a[1]~a[i]的和。则f[i]=Min(f[j]+sum[i]-sum[j])，(1<=j<i)。

我们用一个变量记录i之前所有f[j]-sum[j]的最小值，即可实现O(1)转移。总复杂度为O(n)。

现在难度加大，要求每段最多不超过k个物品。这时我们用单调队列维护一个k区间内f[j]-sum[j]的最小值即可。相信大家都会。

二、转移代价为该段物品的价格之和的平方

即f[i]=Min(f[j]+(sum[i]-sum[j])^2)，(1<=j<i)。

我们把平方拆开，得到f[i]=Min(f[j]+sum[i]^2-2sum[i]sum[j]+sum[j]^2)

中间有一项2sum[i]sum[j]。单调队列懵逼了。

事实上，只要状态转移方程中含有既有sum[i]，又有sum[j]的项（如sum[i]*sum[j]），那么我们就无法使用上述的方法优化。注意，这里的“项”指的是一个单独的项，而sum[i]-sum[j]就不算，因为它是两项。当然，根据题目描述的不同，sum数组有可能被替换为其他数组。

这时，我们今天的主角：斜率优化就要登场了。

状态转移方程的化简与改写

斜率优化算法最重要的一步，就是要将状态转移方程改写为y=kx+b的形式。而这一算法主要的难点就在于，对于一个复杂的状态转移方程，我们将哪些项将作为y，哪些项最为k和x，哪些项作为b。

这既需要掌握普遍性的套路和方法，又需要不断的练习，培养敏感度、熟练度，从而快速、准确地改写状态转移方程。

我们以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-2s[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=2s[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的取值，因此每个决策点都对应了平面直角坐标系里的一个点。为了使我们这条函数图像的截距最小，我们在向上平移的过程中一定先选第一个碰到的点。

pic1

对于任意三个决策点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段的斜率小于CD段的斜率。通俗地讲，我们应该维护“连接相邻两点的线段斜率”单调递增的一个“下凸壳”，只有这个下凸壳的顶点才有可能成为最优决策。实际上，对于一条斜率为k的直线，若某个顶点左侧线段的斜率比k小，右侧线段的斜率比k大，则该顶点就是最优决策。换言之，只要找到了这样一个点，我们就得到了使截距最小化的那个决策j。

单调队列维护凸壳

在本题中，有两个隐藏的条件：

1. 横坐标x，即(s[j]+L)递增。

2. 相邻两点的线段斜率，即2*s[i]也是递增的。

因此我们可以用一个单调队列来维护前文所述的这样一个“凸壳”。对于每个状态变量i：

1. 检查队头的两个决策变量q[l]和q[l+1]，若他们的斜率

   
   

   

   （这里k、x、y就是前面改写状态转移方程得到的k=2*s[i]，x=(s[j]+L)，y=f[j]+(s[j]+L)^2）。

2. 直接取出队头j=q[l]为最优决策，计算出f[i]。

3. 把新决策i从队尾插入。在插入之前，若三个决策点q[r-1]，q[r]，i不满足斜率单调递增（不满足下凸性，即q[r]是无用决策），则直接从队尾让q[r]出队，继续检查新的队尾。

由于每个元素最多入队、出队一次，因此整个算法的时间复杂度为O(n)。

给出例题（玩具装箱）的代码：

//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了。这时往往需要用贪心的方法对决策点进行排序。