首页 OI

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

# 普通斜优

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

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

[HNOI2008]玩具装箱

# 题目描述

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

1⩽n⩽5×1041\leqslant n\leqslant 5\times 10^4，1⩽L,ci⩽1071\leqslant L,c_i\leqslant 10^7

# 输入格式

第一行两个整数，nn 和 LL。

第 22 到第 (n+1)(n+1) 行，第 (i+1)(i+1) 行一个整数 cic_i。

# 输出格式

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

# 样例

样例输入
5 4
3
4
2
1
4
样例输出
1

# 思路

设计 DP。

设 fif_i 表示第 ii 个玩具作为其所处的箱子的结尾的时候，前面所有箱子的总代价的最小值。记 sis_i 为 cic_i 的前缀和，得到 n2n^2 状态转移方程：fi=min⁡1⩽j⩽i(fj+(i−j+si−sj−L−1)2)f_i=\min\limits_{1\leqslant j\leqslant i}\big(f_j+(i-j+s_i-s_j-L-1)^2\big)。记 wiw_i 为 si+is_i+i，得：fi=min⁡1⩽j⩽i(fj+(wi−wj−L−1)2)f_i=\min\limits_{1\leqslant j\leqslant i}\big(f_j+(w_i-w_j-L-1)^2\big)

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

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

# 思考方式

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

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

fj+(wi−wj−L−1)2⩽fk+(wi−wk−L−1)2fj+(wi−L−1)2−2(wi−L−1)wj+wj2⩽fk+(wi−L−1)2−2(wi−L−1)wk+wk2fj−2(wi−L−1)wj+wj2⩽fk−2(wi−L−1)wk+wk2fj−fk+wj2−wk2⩽2(wi−L−1)(wj−wk)\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>kj>k 且 wiw_i 递增，所以 wj−wk>0w_j-w_k>0（可能会遇到等于 00 的情况，需要特判为 INFINF），即：

fj+wj2−(fk+wk2)wj−wk⩽2(wi−L−1)\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}

此处变化的原则是把仅关于 ii 的项和仅关于 jj 的项放在一边，把关于 ii 且关于 jj 的项放在另一边，至于到底在那边并不重要，换边乘 −1-1 就行了。

变化完之后，我们发现如果记 yi=fi+wi2y_i=f_i+w_i^2，xi=wix_i=w_i，那么式子左边就是 yj−ykxj−xk\frac{y_j-y_k}{x_j-x_k}，形如一个直线的斜率。也就是说，如果把决策点按照 (wi,fi+wi2)(w_i,f_i+w_i^2) 为坐标的样子标记在平面直角坐标系上，那么如果决策点 p1p_1 和决策点 p2p_2 (xp1>xp2)(x_{p_1}>x_{p_2}) 的连线的斜率 ⩽2(wi−L−1)\leqslant 2(w_i-L-1) 那么决策点 p1p1 优于决策点 p2p2。

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

进一步的，我们假设有三个候选决策点 p1,p2,p3p_1,p_2,p_3，他们在平面上形如这样：

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

  1. k0<k2<k1k_0<k_2<k_1，此时 p1p_1 优于 p2p_2 优于 p3p_3。
  2. k2⩽k0<k1k_2\leqslant k_0<k_1，此时 p1p_1 优于 p2p_2 且 p3p_3 优于 p2p_2。
  3. k2<k1⩽k0k_2<k_1\leqslant k_0，此时 p3p_3 优于 p2p_2 优于 p1p_1。

综上，在 k1>k2k_1>k_2 的条件下，无论如何决策点 p2p_2 一定是不优的，于是可以把从候选决策点中删除，像这样：

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

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

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

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

在寻找决策点的过程中，我们一定能找到三个决策点 p1,p2,p3p_1,p_2,p_3 满足 kp1,p2⩽k0<kp2,p3k_{p_1,p_2}\leqslant k_0<k_{p_2,p_3}。此时 p2p_2 优于 p1p_1 且优于 p3p_3，基于本题斜率单调递增的性质，其他直线要么 kp<k0k_p<k_0 要么 kp>k0k_p>k_0，他们相应的决策点均不优于 p2p_2，那么我们称 p2p_2 为最优决策点。

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

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

fi=fj+((wi−L−1)−wj)2=fj+(wi−L−1)2−2(wi−L−1)wj+wj2fj+wj2=2(wi−L−1)wj+fi−(wi−L−1)2\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

此处变化的原则是：

  1. 把 gi∗gjg_i*g_j 看成 kxkx。
  2. fif_i 必须在 bb。
  3. yy 只含 gjg_j，并按需与 kxkx 合并。
  4. 如果 kxkx 单减，建议两边同乘 −1-1 使其单增。

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

对于这种划分：

  • yy 为 fj+wj2f_j+w_j^2
  • kk 为 2(wi−L−1)2(w_i-L-1)
  • xx 为 wjw_j
  • bb 为 fi−(wi−L−1)2f_i-(w_i-L-1)^2

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

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

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

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

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

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

# 具体实现

用单调队列 qq 维护凸包，开头为 ss，结尾为 tt，操作如下：

  1. 在凸包上找到最优决策点 jj。
  2. 用 jj 更新 ii。
  3. 把 ii 作为下一个决策点加入平面，更新凸包

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

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

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

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

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

复杂度瓶颈在于操作 1。

# 再优化

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

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

证明见下。

# 四边形不等式

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

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

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

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

∵∀a<c,W(a,c)+W(a+1,c+1)⩽W(a+1,c)+W(a,c+1)\because\forall a<c,W(a,c)+W(a+1,c+1)\leqslant W(a+1,c)+W(a,c+1)

(1)

∴∀a+1<c,W(a+1,c)+W(a+2,c+1)⩽W(a+2,c)+W(a+1,c+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)(1)、(2)(2) 式相加：W(a,c)+W(a+2,c+1)⩽W(a+2,c)+W(a,c+1)W(a,c)+W(a+2,c+1)\leqslant W(a+2,c)+W(a,c+1)

进一步地：∴∀a⩽b⩽c,W(a,c)+W(b,c+1)⩽W(b,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)

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

证毕。

# 决策单调性

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

∵ti\because t_i 在 fif_i 的决策点中最优

∴∀i∈[1,n],j∈[0,ti),fti+W(ti,i)⩽fj+W(j,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)

又 ∵∀k∈(i,n],j<ti<i<k\because\forall k\in(i,n],j<t_i<i<k，且函数 ww 满足四边形不等式

∴W(j,i)+W(ti,k)⩽W(j,k)+W(ti,i)\therefore W(j,i)+W(t_i,k)\leqslant W(j,k)+W(t_i,i)

∴W(ti,k)−W(ti,i)⩽W(j,k)−W(j,i)\therefore W(t_i,k)-W(t_i,i)\leqslant W(j,k)-W(j,i)

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

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

证毕。

# 证明决策单调性

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

# 四边形不等式法

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

记 Q=wi−wj−L−1Q=w_i-w_j-L-1

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

∴W(i+1,j+1)=(wi+1−wj+1−L−1)2=((si+1+i+1)−(sj+1+j+1)−L−1)2=((si+ci+1+i+1)−(sj+cj+1+j+1)−L−1)2=((si+i)−(sj+j)−L−1+ci+1−cj+1)2=((wi−wj−L−1)+ci+1−cj+1)2=(Q+ci+1−cj+1)2,W(i,j+1)=(wi−wj+1−L−1)2=(wi−(sj+1+j+1)−L−1)2=(wi−(sj+cj+1+j+1)−L−1)2=(wi−(sj+j)−L−1−cj+1−1)2=((wi−wj−L−1)−cj+1−1)2=(Q−cj+1−1)2,W(i+1,j)=(wi+1−wj−L−1)2=((si+1+i+1)−wj−L−1)2=((si+ci+1+i+1)−wj−L−1)2=((si+i)−wj−L−1+ci+1+1)2=((wi−wj−L−1)+ci+1+1)2=(Q+ci+1+1)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}

∴W(i,j)+W(i+1,j+1)=2Q2+2Qci+1−2Qcj+1+ci+12−2ci+1cj+1+cj+12,W(i+1,j)+W(i,j+1)=2Q2+2Qci+1+ci+12+2ci+1+2−2Qcj+1+cj+12+2cj+1\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}

∴W(i,j)+W(i+1,j+1)−W(i+1,j)−W(i,j+1)=−2−2ci+1−2cj+1−2ci+1cj+1=−2(ci+1+1)(cj+1+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}

又 ∵ci,cj≥1\because c_i,c_j\geq1

∴−2(ci+1+1)(cj+1+1)⩽−8<0\therefore-2(c_{i+1}+1)(c_{j+1}+1)\leqslant-8<0

∴W(i,j)+W(i+1,j+1)⩽W(i+1,j)+W(i,j+1)\therefore W(i,j)+W(i+1,j+1)\leqslant W(i+1,j)+W(i,j+1)

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

证毕。

# 数形法

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

证毕。

# 线性规划法

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

证毕。

# 再实现

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

根据决策单调性，后面决策点的最优决策点一定在队首后面，且每个决策点至多进出队列 1 次，时间复杂度 O(n)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;
}
# 注意事项
斜率优化代码一般很短，但是细节较多，简单列举一下：
  1. 尽量不计算斜率，用交叉相乘，防止丢精。
  2. 判断是否需要在队列里插入初始值，如例题。
  3. 一般来说，可以出队的边界情况是 head<tail 。
  4. 如 xix_i 可能出现相等的情况：如果你使用的是交叉相乘，那你不用额外做什么；如果你计算了斜率，那就要特判一下 x[i]==x[j]?INF:... 。
  5. 一定要根据决策的优劣、题目要求的 min/maxmin/max 来判断要维护上凸还是下凸包。
  6. 交叉相乘的时候，尽量把乘出去的 x[j]-x[i] 弄成正数，这样就不用考虑变号的问题了。
  7. 建议比较都用 <= 或 >= 代替 < 或 > ，因为斜率相等的点取那个都无所谓，这样还可以去重。
  8. 注意看交叉相乘会不会炸 long long ，会的话换 double ，输出注意转整型。
  9. 一定要计算斜率的话要用 long double 。
  10. 注意 xix_i 及斜率的单调性，不满足单调的要使用其他方法，见下文。
# 不单调斜优
不单调，即斜优的某些元素不单调，如下：
# 斜率不单调
亦可解释为最优决策点不单调，就是不能证明决策单调性，此时不能再弹出队首，只能二分。
# 横坐标不单调
此时插入决策点时可能会插在凸包中间，而队列不支持这种操作。
可以使用平衡树实现插入、查找前驱操作，或着用 CDQ 分治提供单调性，具体见下。
也可使用李超线段树，但是我不会（
# 斜率、横坐标均不单调
用平衡树。把 k0k_0 放到平衡树上找前驱，再更新 dp 值，最后 insert 。
用 CDQCDQ，步骤如下：
  1. 把 xix_i 小于 midmid 的点作为左区间，其余作为右区间（如果 xix_i 单调则原区间的左区间就是左区间，右区间就是右区间）。
  2. 递归左区间。
  3. 对于左区间用单调队列维护出凸包（正确性见下），用它更新右区间。
  4. 递归右区间。
  5. 最后对整个区间对 xix_i 排序，此时这个区间 xix_i 单调，上一级区间可以直接对于本区间维护凸包，步骤 3 正确性得证。
# 练习
# 普通斜优
[ZJOI2007] 仓库建设
[APIO2014] 序列分割
[APIO2010] 特别行动队
[CEOI2004] 锯木厂选址
[NOIP2018 普及组] 摆渡车
[USACO08MAR] Land Acquisition G
[SDOI2016] 征途
[JSOI2009] 火星藏宝图
丝之割
[COCI2018-2019#4] Akvizna
[NOI2016] 国王饮水记
# 不单调斜优
任务安排 & [SDOI2012] 任务安排
[NOI2007] 货币兑换
[CEOI2017] Building Bridges
[SDOI2012] 基站建设
[NOI2014] 购票
# 参考资料
  1. ChatGPT
  2. 辰星凌的博客
  3. OI-wiki
  4. 其他大佬的博客
 
 更新于   阅读次数  次