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

具体地，序列里的每样物品有一个价值值a[i]，我们用 $sum[i]表示a[1]sim 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$ 的形式：

我们令既有 $s[i]，又有s[j]的项为kx；$
$令含有f[j]的项以及其他所有含有s[j]的项为y；$
$令f[i]和剩余所有的项为b$
$更具体地，在kx里，包含s[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。

单调队列维护凸壳
在本题中，有两个隐藏的条件：

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

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

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

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

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

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

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