之前研究过一段时间的斜率优化，总觉的什么时候该写写。

普通斜优

斜率优化是一种优化DP的方法，主要应用于 $1D/1D$ 的转移中（也有反例），一般可以把复杂度优化成 $O(n)$ 或 $O(n\log n)$。斜率优化主要利用了++单调性++{.wavy}，所以在阅读下文之前，请至少熟练掌握++单调队列++{.wavy}。

本文以下面这道题为例讲解斜率优化，并对涉及到的一些本题之外的问题，在后文提供练习题。

+++ [HNOI2008]玩具装箱

题目描述

有 $n$ 个玩具，第 $i$ 个长度为 $c_i$。将第 $i$ 到第 $j$ 个玩具装到一个箱子里会花费 $(j-i+\sum\limits_{k=i}^jc_k-L)^2$ 的代价。求总代价最小值。

$1\leqslant n\leqslant 5\times 10^4$，$1\leqslant L,c_i\leqslant 10^7$

输入格式

第一行两个整数，$n$ 和 $L$。

第 $2$ 到第 $(n+1)$ 行，第 $(i+1)$ 行一个整数 $c_i$。

输出格式

一行一个整数代表最小总代价。

样例

+++

思路

设计DP。

设 $f_i$ 表示第 $i$ 个玩具作为其所处的箱子的结尾的时候，前面所有箱子的总代价的最小值。记 $s_i$ 为 $c_i$ 的前缀和，得到 $n^2$ 状态转移方程：$f_i=\min\limits_{1\leqslant j\leqslant i}\big(f_j+(i-j+s_i-s_j-L-1)^2\big)$。记 $w_i$ 为 $s_i+i$，得：$f_i=\min\limits_{1\leqslant j\leqslant i}\big(f_j+(w_i-w_j-L-1)^2\big)$

至于为什么后面要 $-1$？是因为实质上是第 $(j+1)$ 个到第 $i$ 个玩具装到一个箱子中所以是 $i-(j+1)=i-j-1$ !!应该只有我一开始不知道吧!!。

现在这个转移是 $n^2$ 的，显然会炸，考虑优化。

思考方式

下面将以两种思维解释斜优的过程：数形结合和线性规划。

;;;id1 数形结合

先变化一下转移，变化的方法在后面给出，这样变化的好处也会体现。假设现在有两个决策点 $j,k$$(j>k)$，而从 $j$ 转移到 $i$ 比从 $k$ 转移到 $i$ 优，即：

$$
\begin{aligned}
f_j+(w_i-w_j-L-1)^2&\leqslant f_k+(w_i-w_k-L-1)^2\
f_j+(w_i-L-1)^2-2(w_i-L-1)w_j+w_j^2&\leqslant f_k+(w_i-L-1)^2-2(w_i-L-1)w_k+w_k^2\
f_j-2(w_i-L-1)w_j+w_j^2&\leqslant f_k-2(w_i-L-1)w_k+w_k^2\
f_j-f_k+w_j^2-w_k^2&\leqslant 2(w_i-L-1)(w_j-w_k)
\end{aligned}
$$

由于 $j>k$ 且 $w_i$ 递增，所以 $w_j-w_k>0$（可能会遇到等于 $0$ 的情况，需要特判为 $INF$），即：

$$
\begin{aligned}
\frac {f_j+w_j^2-(f_k+w_k^2)}{w_j-w_k}&\leqslant 2(w_i-L-1)
\end{aligned}
$$

此处变化的原则是把++仅关于 $i$ 的项++{.dot}和++仅关于 $j$ 的项++{.dot}放在一边，把++关于 $i$ 且关于 $j$ 的项++{.dot}放在另一边，至于到底在那边并不重要，换边乘 $-1$ 就行了。

变化完之后，我们发现如果记 $y_i=f_i+w_i^2$，$x_i=w_i$，那么式子左边就是 $\frac{y_j-y_k}{x_j-x_k}$，形如一个直线的斜率。也就是说，如果把决策点按照 $(w_i,f_i+w_i^2)$ 为坐标的样子标记在平面直角坐标系上，那么如果决策点 $p_1$ 和决策点 $p_2$ $(x_{p_1}>x_{p_2})$ 的连线的斜率 $\leqslant 2(w_i-L-1)$ 那么决策点 $p1$ 优于决策点 $p2$。

:::info
对于刚学斜优的同学，为避免麻烦的细节处理，可以把斜优模板化。比如此处建议尽量把最终的式子化为 $\frac{y_j-y_k}{x_j-x_k}$ 的形式，而不是 $\frac{y_k-y_j}{x_j-x_k}$。!!熟练掌握之后倒也无所谓!!
:::

进一步的，我们假设有三个++候选决策点++{.wavy} $p_1,p_2,p_3$，他们在平面上形如这样：

{height=”400px” width=”400px”}

他们满足条件：$k_1>k_2$。记 $2(w_i-L-1)$ 为 $k_0$，那么接下来 $k_1,k_2$ 与 $k_0$ 的关系有以下几种：

$k_0<k_2<k_1$，此时 $p_1$ 优于 $p_2$ 优于 $p_3$。
$k_2\leqslant k_0<k_1$，此时 $p_1$ 优于 $p_2$ 且 $p_3$ 优于 $p_2$。
$k_2<k_1\leqslant k_0$，此时 $p_3$ 优于 $p_2$ 优于 $p_1$。

综上，在 $k_1>k_2$ 的条件下，无论如何决策点 $p_2$ 一定是++不优的++{.wavy}，于是可以把从候选决策点中删除，像这样：

{height=”400px” width=”400px”}

再把三个点扩展到平面上的很多点，对于任意三个点进行上述操作。在本题中，剩下的点++从左到右++{.dot}依次连线形成的直线的斜率++单调递增++{.wavy}。这样连线画图的结果就像一个++下凸包++{.wavy}。

所有内角大小都在 $[0,\pi]$ 范围内的简单多边形叫凸多边形。

在平面上能包含所有给定点（即具有凸性）的最小凸多边形叫做凸包。

下凸包就是凸包的下半部分。如图是维护的下凸包的例子：

{height=”400px” width=”400px”}

在寻找决策点的过程中，我们一定能找到三个决策点 $p_1,p_2,p_3$ 满足 $k_{p_1,p_2}\leqslant k_0<k_{p_2,p_3}$。此时 $p_2$ 优于 $p_1$ 且优于 $p_3$，基于本题斜率单调递增的性质，其他直线要么 $k_p<k_0$ 要么 $k_p>k_0$，他们相应的决策点均不优于 $p_2$，那么我们称 $p_2$ 为++最优决策点++{.wavy}。

在已经维护好的下凸包上，从前往后依次找到第一个斜率大于 $k_0$ 的线段，它的左端点就是最优决策点。由于维护好的凸包从左往右斜率单调，所以可以二分找到最优决策点。

;;;

;;;id1 线性规划

忽略 $\min$，把上面的式子变化成 $y=kx+b$ 的形式，即：

$$
\begin{aligned}
f_i&=f_j+\big((w_i-L-1)-w_j\big)^2\
&=f_j+(w_i-L-1)^2-2(w_i-L-1)w_j+w_j^2
\end{aligned}\
f_j+w_j^2=2(w_i-L-1)w_j+f_i-(w_i-L-1)^2
$$

此处变化的原则是：

把 $g_i*g_j$ 看成 $kx$。
$f_i$ 必须在 $b$。
$y$ 只含 $g_j$，并++按需++{.dot}与 $kx$ 合并。
如果 $kx$ 单减，建议两边同乘 $-1$ 使其单增。

:::danger
注意，划分方式不止一种。
:::

对于这种划分：

$y$ 为 $f_j+w_j^2$
$k$ 为 $2(w_i-L-1)$
$x$ 为 $w_j$
$b$ 为 $f_i-(w_i-L-1)^2$

假如有一堆点在平面上长这样：

{height=”400px” width=”400px”}

我们的目的是使 $f_i$ 最小，即使 $b=f_i-(w_i-L-1)^2$ 最小，就是要求一个过一点的斜率为 $2(w_i-L-1)$ 直线使其截距最小，转为线性规划问题。

那么最优决策点就很好找了：

{height=”400px” width=”400px”}

图中 $F$ 即为最优决策点，且最优决策点必然处于凸包上。

;;;

即便有两种思路，但是建议结合使用：

在思考前，主要利用代数法转换方程，确定斜率形式。
在思考阶段建议多用线性规划思想，利用图形直观感受，更好得判断单调性（后文会讲）。

具体实现

用单调队列 $q$ 维护凸包，开头为 $s$，结尾为 $t$，操作如下：

在凸包上找到最优决策点 $j$。
用 $j$ 更新 $i$。
把 $i$ 作为下一个决策点加入平面，更新凸包

对于操作3，比较 $q_{t-1}$、$q_t$ 和 $i$，看是否能删掉 $q_t$：能删就删，重复操作3；不能删就把 $i$ 加入队列。

判断能否删点有两种方法（可以结合上文“数形结合”中的图理解）：

slope(q[t],q[t-1])>slope(q[t],i)
slope(q[t],q[t-1])>slope(q[t-1],i)

两者是等价的，可把 q[t] 删除，读者自己思考。

对于操作1，暴力找的话复杂度还是 $O(n^2)$，二分查找可使复杂度降为 $O(n\log n)$。

复杂度瓶颈在于操作1。

再优化

如果要继续降低复杂度的话，将要利用++决策单调性++{.wavy}，其简单定义为：

对于形如 $f_i=f_j+W(i,j)$的方程，即 $1D/1D$ 转移方程，设 $t_i$ 表示 $f_i$ 的最优决策点。那么决策单调性可表示为 $\forall j\leqslant k,t_j\leqslant t_k$。也就是说 $t_i$ 不降。

证明见下。

四边形不等式

设二元函数 $W(x,y)$ 定义域为整数。若 $\forall a\leqslant b\leqslant c\leqslant d,W(a,c)+W(b,d)\leqslant W(a,d)+W(b,c)$，那么函数 $W(x,y)$ 满足++四边形不等式++{.wavy}。

从形的角度来看，把 $W(x,y)$ 画成这样：

{height=”400px” width=”400px”}

那么满足左下角加右上角小于等于左上角加右下角的 $W(x,y)$ 满足四边形不等式。

四边形不等式也可表示为 $\forall a<b,W(a,b)+W(a+1,b+1)\leqslant W(a+1,b)+W(a,b+1)$，证明如下：

$\because\forall a<c,W(a,c)+W(a+1,c+1)\leqslant W(a+1,c)+W(a,c+1)$

(1)

$\therefore\forall a+1<c,W(a+1,c)+W(a+2,c+1)\leqslant W(a+2,c)+W(a+1,c+1)$

(2)

$(1)$、$(2)$ 式相加：$W(a,c)+W(a+2,c+1)\leqslant W(a+2,c)+W(a,c+1)$

进一步地：$\therefore\forall a\leqslant b\leqslant c,W(a,c)+W(b,c+1)\leqslant W(b,c)+W(a,c+1)$

同理：$\therefore\forall a\leqslant b\leqslant c\leqslant d,W(a,c)+W(b,d)\leqslant W(b,c)+W(a,d)$

证毕。

决策单调性

对于一个 $1D/1D$ 的转移方程 $f_i=f_j+W(i,j)$，函数 $w$ 满足四边形不等式是其满足决策单调性的充分条件证明如下：

$\because t_i$ 在 $f_i$ 的决策点中最优

$\therefore\forall i\in[1,n],j\in[0,t_i),f_{t_i}+W(t_i,i)\leqslant f_j+W(j,i)$

(3)

又 $\because\forall k\in(i,n],j<t_i<i<k$，且函数 $w$ 满足四边形不等式

$\therefore W(j,i)+W(t_i,k)\leqslant W(j,k)+W(t_i,i)$

$\therefore W(t_i,k)-W(t_i,i)\leqslant W(j,k)-W(j,i)$

与 $(3)$ 式相加得：$f_{t_i}+W(t_i,k)\leqslant f_j+W(j,k)$

也就是说，从任意在 $i$ 的最优决策点 $t_i$ 之前的决策点，转移到 $i$ 后面任意一个决策点都没有从 $t_i$ 转移优。那么对于 $i$ 之后的决策点 $k$，他的最优决策点一定属于 $[t_i,k)$，那么 $t_i$ 不减，决策具有单调性。

证毕。

证明决策单调性

提供三种方法，后两种与前面的思考方式有关。

四边形不等式法

本题转移方程形如 $f_i=f_j+W(i,j)$，其中 $W(i,j)=(w_i-w_j-L-1)^2$，证明如下：

记 $Q=w_i-w_j-L-1$

$\therefore W(i,j)=Q^2$

$
\begin{aligned}
\therefore W(i+1,j+1)&=(w_{i+1}-w_{j+1}-L-1)^2\
&=\big((s_{i+1}+i+1)-(s_{j+1}+j+1)-L-1\big)^2\
&=\big((s_i+c_{i+1}+i+1)-(s_j+c_{j+1}+j+1)-L-1\big)^2\
&=\big((s_i+i)-(s_j+j)-L-1+c_{i+1}-c_{j+1}\big)^2\
&=\big((w_i-w_j-L-1)+c_{i+1}-c_{j+1}\big)^2\
&=\big(Q+c_{i+1}-c_{j+1}\big)^2,
\end{aligned}\
\begin{aligned}
W(i,j+1)&=(w_i-w_{j+1}-L-1)^2\
&=\big(w_i-(s_{j+1}+j+1)-L-1\big)^2\
&=\big(w_i-(s_j+c_{j+1}+j+1)-L-1\big)^2\
&=\big(w_i-(s_j+j)-L-1-c_{j+1}-1\big)^2\
&=\big((w_i-w_j-L-1)-c_{j+1}-1\big)^2\
&=\big(Q-c_{j+1}-1\big)^2,
\end{aligned}\
\begin{aligned}
W(i+1,j)&=(w_{i+1}-w_j-L-1)^2\
&=\big((s_{i+1}+i+1)-w_j-L-1\big)^2\
&=\big((s_i+c_{i+1}+i+1)-w_j-L-1\big)^2\
&=\big((s_i+i)-w_j-L-1+c_{i+1}+1\big)^2\
&=\big((w_i-w_j-L-1)+c_{i+1}+1\big)^2\
&=\big(Q+c_{i+1}+1\big)^2
\end{aligned}
$

$
\therefore W(i,j)+W(i+1,j+1)=2Q^2+2Qc_{i+1}-2Qc_{j+1}+c_{i+1}^2-2c_{i+1}c_{j+1}+c_{j+1}^2,\
W(i+1,j)+W(i,j+1)=2Q^2+2Qc_{i+1}+c_{i+1}^2+2c_{i+1}+2-2Qc_{j+1}+c_{j+1}^2+2c_{j+1}
$

$
\begin{aligned}
\therefore W(i,j)+W(i+1,j+1)-W(i+1,j)-W(i,j+1)&=-2-2c_{i+1}-2c_{j+1}-2c_{i+1}c_{j+1}\
&=-2(c_{i+1}+1)(c_{j+1}+1)
\end{aligned}
$

又 $\because c_i,c_j\geq1$

$\therefore-2(c_{i+1}+1)(c_{j+1}+1)\leqslant-8<0$

$\therefore W(i,j)+W(i+1,j+1)\leqslant W(i+1,j)+W(i,j+1)$

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

证毕。

数形法

由于 $k_0=2(w_i-L-1)$ 单增，所以第一个斜率大于 $k_0$ 的线段逐渐往后移，最优决策点后移，即最优决策点的位置单增。

证毕。

线性规划法

由于直线斜率 $2(w_i-L-1)$ 单增，故其与凸包的切点横坐标单增，最优决策点的位置单增。

证毕。

再实现

对于上面的实现方法，我们只用更改操作1：在第一根线段的斜率小于等于 $k_0$ 时弹出队首，重复直至第一根线段的斜率大于 $k_0$，此时队首即为最优决策点。

根据决策单调性，后面决策点的最优决策点一定在队首后面，且每个决策点++至多++{.dot}进出队列1次，时间复杂度 $O(n)$。

本题代码

基于上面的方法，建议自己实现一遍，再看我的代码。

#include <bits/stdc++.h>
#define db double
using namespace std;
const int N=50005;
int n,L;
db c[N],s[N],f[N];
int head,tail,Q[N];

inline db w(int i){return s[i]+i;}
inline db X(int i){return w(i);}
inline db Y(int i){return f[i]+w(i)*w(i);}
inline db slope(int i,int j){return (Y(i)-Y(j))/(X(i)-X(j));}

int main(){
    scanf("%d%d",&n,&L);
    for(int i=1;i<=n;i++) scanf("%lf",&c[i]);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+c[i];

    head=tail=1;
    //注意此时队列中已经有一个决策点j=0，f[1]需要从这里转移
    for(int i=1;i<=n;i++){
        while(head<tail&&slope(Q[head],Q[head+1])<=2*(w(i)-L-1)) ++head;
        //寻找最优决策点，并把前面的点弹出。
        f[i]=f[Q[head]]+(w(i)-w(Q[head])-L-1)*(w(i)-w(Q[head])-L-1);
        //用最优决策点（即队首）更新f[i]。
        while(head<tail&&slope(i,Q[tail-1])<=slope(Q[tail-1],Q[tail])) --tail;
        //把i当作决策点维护凸包，把队尾不符合凸包凸性的决策点弹出。
        Q[++tail]=i;
        //把i加入凸包。
    }

    printf("%lld\n",(long long)f[n]);
    return 0;
}

但是一般不建议这样写，除法容易丢精度，所以我们把斜率的除换成交叉相乘：

#include <bits/stdc++.h>
#define db double
using namespace std;
const int N=50005;
int n,L;
db c[N],s[N],f[N];
int head,tail,Q[N];
inline db w(int i){return s[i]+i;}
inline db X(int i){return w(i);}
inline db Y(int i){return f[i]+w(i)*w(i);}
inline int chk1(int i,int j,int p){return Y(j)-Y(i)<=2ll*(w(p)-L-1)*(X(j)-X(i));}
inline int chk2(int i,int j,int p){return (Y(p)-Y(i))*(X(j)-X(i))<=(Y(j)-Y(i))*(X(p)-X(i));}
//要卡常的话可以不写函数，直接写表达式
int main(){
    scanf("%d%d",&n,&L);
    for(int i=1;i<=n;i++) scanf("%lf",&c[i]);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+c[i];
    head=tail=1;
    for(int i=1;i<=n;i++){
        while(head<tail&&chk1(Q[head],Q[head+1],i)) ++head;
        f[i]=f[Q[head]]+(w(i)-w(Q[head])-L-1)*(w(i)-w(Q[head])-L-1);
        while(head<tail&&chk2(Q[tail-1],Q[tail],i)) --tail;
        Q[++tail]=i;
    }
    printf("%lld\n",(long long)f[n]);
    return 0;
}