四边形不等式&决策单调性

立柱已选162534 · 2024-04-26 08:59:56 · 算法·理论

原 PPT

理论上是我的 sky 课件，但是没讲，所以成为了一篇专栏。

updated on 2025.4.26

一周年纪念，回来看一眼并修 markdown。

typst 更新后因未知原因坠机，只能在这更新了（

updated on 2025.8.8~2025.8.13

最新最热分治出炉，加入相关解释。

渲染更新，修 markdown 并加入折叠框。

投了全站推荐。

updated on 2026.1.8

大改，现在人类能够看懂了，同时改掉了一些错误。

updated on 2026.2.28

代码排版炸了，修改。

一、四边形不等式

\ 定义 1：已知 w_{x,y}(1 \leq x < y \leq n)，若对任意 x_{1} \leq x_{2} \leq y_{1} \leq y_{2} 有 w_{x_{1},y_{1}} + w_{x_{2},y_{2}} \leq w_{x_{1},y_{2}} + w_{x_{2},y_{1}}（交叉优于包含），则称原函数满足四边形不等式。

:::info[为什么它叫四边形不等式]

在凸四边形 ABCD 中，AC+BD\ge AD+BC（证明考虑对 \Delta AOD 和 \Delta BOC 分别使用三角形两边之和大于第三边），发现这和四边形不等式形式完全一样只是符号反过来了。

定义 2：若对任意 x,y(x \leq y) 有 w_{x,y} + w_{x + 1,y + 1} \leq w_{x,y + 1} + w_{x,y + 1}，则称原函数满足四边形不等式。

这两个定义是等价的。

• 若将定义 1 的 x_1,x_2,y_1,y_2 分别设为 x,x + 1,y,y + 1，就是定义 2 的形式。

• 考虑对定义 2 使用数学归纳法，若对 x_{1},x_{2},y_{1},y_{2} 与 x_{2},x_{3},y_{1},y_{2} 已经满足四边形不等式，x_{1},x_{3},y_{1},y_{2} 也满足四边形不等式，那么就可以由 x,x + 1,y,y + 1 推至 x,x',y,y + 1，在 y 方向同理。

:::info[证明]

形象一点地来讲：

考虑这么一个方格，其中第 (i,j) 格填的是 w_{i,j}。

这两张图分别代表 x_1,x_2,y_1,y_2 与 x_2,x_3,y_1,y_2 的四边形不等式，不等式表示红色部分之和 \le 绿色部分之和。

将红绿两色部分分别加起来：

由于红绿两色分别对应不等式的两侧，因此可以消去相同的部分，再加起来得：

由此，可得验证四边形不等式的代码如下：

for(int i=1;i<n;++i)
   for(int j=i;j<n;++j)
   assert(w(i,j)+w(i+1,j+1)<=w(i,j+1)+w(i+1,j));

如果程序没有出现报错，那么四边形不等式成立。

在考场上一般用这种方法判定四边形不等式，而在实际证明中一般会使用倒推法，将 w 带进四边形不等式的定义中证明其成立。

容易发现，在四边形不等式中任何只关于 x 或 y 的项都可以在证明中被消去。

严格来说，设 w_{x,y} = w'_{x,y} + g_{x} + g_{y}，而 w'_{x,y} 满足四边形不等式，则 w_{x,y} 满足四边形不等式。

证明：

二、决策单调性及对应优化

\ 首先，看已知满足四边形不等式的 w_{j,i}(1 \leq j < i \leq n) 时，如何快速求所有 f_{i} = \min\limits_{j \leq i}w_{j,i}。

本文中定义 i 为状态点，j 为决策点。

对于每个状态点 i，令 p_{i} 表示在该状态点对应的最优决策点，即当 j = p_{i} 时 w_{j,i} = f_{i}，不妨设 p_{i} 为第一个满足条件的点。

决策单调性：\forall i < i',p_{i} \leq p_{i'}

注意：根据决策单调性直接暴力计算不会优化时间复杂度，如果 p_{1} = p_{2} = \ldots = p_{n} = 1，那么还是要枚举 O(n^2) 个决策点。

由四边形不等式可以推知决策单调性

考虑用反证法，设 \exists i' < i,p_{i'} > p_{i}。

对 p_{i},p_{i'},i',i 应用四边形不等式可得\

而由于上面的定义，w_{p_{i},i'} > w_{p_{i'},i'},w_{p_{i'},i} \geq w_{p_{i},i}

显然矛盾，故决策单调性成立。

对于以上内容，将 \min 换为 \max（w_{x_1,y_1}+w_{x_2,y_2} \ge w_{x_1,y_2}+w_{x_2,y_1}，f_i=\max\limits _{j \le i}w_{j,i}）后也可以用类似的方法证明。

这种情况下判定代码如下：

for(int i=1;i<n;++i)
   for(int j=i;j<n;++j)
   assert(w(i,j)+w(i+1,j+1)>=w(i,j+1)+w(i+1,j));

为方便考虑，以下内容只考虑 \min 的形式，\max 是同理的。

已知决策单调性后的一些优化

对于之前的问题，若满足决策单调性，有几个方法优化。

0. 单调队列与斜率优化

和主题无关，不讲。

1. 分治

这里分治的是状态点，同时会下传当前可能的决策点。

对于每个状态点区间 [ l,r] 及可能决策点范围 [L,R]，设它的中点为 \text{mid}，先扫一遍 [L,R] 求出 p_{\text{mid}}。

由于决策单调性，计算 [l,\text{mid}) 时的可能决策点只有 L\sim p_{\text{mid}}，在计算 (\text{mid},r] 时的可能决策点只有 p_{\text{mid}}\sim R，递归做即可。

显然每一层的计算量均为 O(n)，共递归 O\left( \log n \right) 层，所以总计算量为 O\left( n\log n \right)。

参考代码，注意可能 R\ge \text{mid}，此时 [\text{mid},R] 范围内的决策点不参与 f_\text{mid} 的计算：

:::info[code]

void solve(int l,int r,int L,int R){
        //l与r代表要求区间[l,r]的f，L与R代表p的范围
    int mid=(l+r)>>1;
    for(int i=L;i<=min(mid-1,R);++i)
        if(w(i,mid)<f[mid])f[mid]=w(i,mid),p[mid]=i;
    if(mid>l)solve(l,mid-1,L,p[mid]);
    if(mid<r)solve(mid+1,r,p[mid],R);
}

:::

2. 单调队列 + 二分

为了能处理 DP 转移（半在线），考虑从前往后枚举状态点，加入当前状态点为决策点并维护所有的决策点。

考虑每一个决策点，由于 p_{i} \leq p_{i + 1}，它能够作为一段状态点的最优决策点，然后就永远不行了。

于是在加入决策点时二分这一段状态点的范围（不妨设决策点 j 的范围为 \left[ l_{j},r_{j} \right]），然后用单调队列维护目前可行的所有决策点。

具体来说，当考虑状态点 i 时，先弹出过时的队头（即 r_{j} < i 的队头），拿剩下的队头 j 计算 f_i，然后尝试将决策点 i 入队。

• 如果队列为空，直接入队，此时 l_{i} = i + 1,r_{i} = n。

• 否则，设队尾为 j'。

  • 如果 i 比 j' 劣，将 i 拼在 j' 的后面，即 l_{i} = r_{j} + 1,r_{i} = n。注意这种情况需要入队当且仅当 r_{j'} < n，出现这种情况是因为 r_{j'} = n 的队尾被出队了（见下文）。

  • 否则，分两类讨论 i 比 j' 优，需要入队的情况：

    • 若对 \left[ l_{j'},r_{j'} \right]，i 均比 j' 更优，将 j' 出队。由于 i \geq j' 与决策单调性，只需要判断 w_{j',l_{j'}} > w_{i,l_{j'}} 即可，这种情况可能会多次出现。

    • 若对 \left[ l_{j'},r_{j'} \right] 中的一部分，i 比 j' 更优，将 i 入队并用二分判断 i 开始比 j' 更优的位置，设这个位置为 k 则 r_{q'} = k - 1,l_{i} = k,r_{i} = n。

同样需要注意计算 w_{j,i} 时不能有 j>i，代码实现如下（免责声明：不包对）：

:::info[code]

deque<int> q;
l[1]=1,r[1]=n;
q.push_back(1);
for(int i=2;i<=n;++i){
    while(!q.empty()&&i>r[q.front()])q.pop_front();//处理过时元素
    ans[i]=w(q.front(),i),fr[i]=q.front();
    while(!q.empty()&&w(q.back(),l[q.back()])>=w(i,l[q.back()]))
        q.pop_back();//处理 i 完全优于 j' 的情况
    if(q.empty()){//处理队列为空的情况
        q.push_back(i);
        l[i]=i+1,r[i]=n;
    }
    else if(w(q.back(),r[q.back()])<w(i,r[q.back()])){
        if(r[q.back()]<n){//将i接在j'后面
            q.push_back(i);
            l[i]=r[q.back()]+1,r[i]=n;
        }
    }
    else{
        int L=l[q.back()],R=r[q.back()],mid,p;
        while(R>=L){//二分
            mid=(R+L)/2;
            if(w(q.back(),mid)>=w(i,mid))p=mid,R=mid-1;//记录i开始优于j'的时间
            else L=mid+1;
        }
        r[q.back()]=p-1,l[i]=p,r[i]=n;
        q.push_back(i);
    }
}

:::

也可以类似斜率优化，每次入队和出队时直接二分计算临界点，时间复杂度不变，但是这样二分次数比较多（我也不想写），不提供代码。

3. 最新最热分治（丐版 LARSCH 算法）

这个东西递归的也是状态点。

分治难以处理 DP 转移（半在线）的原因在于 p_{\text{mid}} 依赖 [l,\text{mid}) 的答案，所以考虑放弃求出 p_{\text{mid}} 的精确值，而是保证只考虑 [0,l] 时 p_{\text{mid}} 的正确性。

记只考虑 [0,l] 时 r 的最优决策点为 p_{r,l}，可以发现要递归下去我们需要 p_{\text{mid},l} 与 p_{r,\text{mid}}，前者可以在进入递归后枚举 [p_{l},p_{r,l}] 范围内的决策点算出，后者可以在向左递归后暴力枚举状态点 (l,\text{mid}] 为决策点算出。

惊人地发现，这样确实算出了所有点正确的 f_i 与 p_{i}。

模仿原文，下文选择递归 [l,\text{mid}] 与 [\text{mid},r]，其实递归 [l,\text{mid}-1] 与 [\text{mid}+1,r] 并改一下下标也是对的。

具体步骤如下：

• 预处理 p_1、p_{n,1}

• 进入递归，在 [p_l,p_{r,l}] 求 p_{\text{mid},l}

• 递归 [l,\text{mid}]，得到 p_{l+1}\dots p_{\text{mid}}

• 扫一遍 [l+1,\text{mid}] 求出 p_{r,\text{mid}}

• 递归 [\text{mid},r]，得到 p_{\text{mid}+1}\dots p_r

• 当 r=l+1 时计算原地转移，结束递归

生动形象（？地，下图按递归顺序展示了递归的过程，奇数行表示当前考虑的区间，浅色部分表示 r，蓝色像素点表示 \text{mid}，偶数行（紫色）表示向左递归结束后状态点 r 已经考虑到的区间（浅色在递归前已算出，深色在递归 [l,\text{mid}] 时算出）

显然，时间复杂度不变。

代码实现如下：

:::info[code]

void solve(int l,int r){
    if(r==l+1){
        if(w(r,r)<dp[r])dp[r]=w(r,r),p[r]=r;
        return;
    }
    int mid=(l+r)>>1;
    p[mid]=p[l],dp[mid]=w(p[mid],mid);
    for(int i=p[l]+1;i<=p[r];++i)
        if(w(i,mid)<dp[mid])dp[mid]=w(i,mid),p[mid]=i;
    solve(l,mid);
    for(int i=l+1;i<=mid;++i)
        if(w(i,r)<dp[r])dp[r]=w(i,r),p[r]=i;
    solve(mid,r);
}

:::

4. 其它做法

SMAKW 等，可以做到支持半在线的 O(n)。

例题

三、四边形不等式（决策单调性）实战

例题 1：lightning conductor（四边形不等式证明 / 特殊情况下二分队列优化到 O(n) ）

\ 给定一个长度为 n 的序列 \left\{ a_{n} \right\}，对于每个 i \in [ 1,n]，求出一个最小的非负整数 p，使得 \forall j \in [ 1,n],a_{j} \leq a_{i} + p - \sqrt{|i - j|}

化简得 - \sqrt{y_{1} - x_{1}} - \sqrt{y_{2} - x_{2}} \leq - \sqrt{y_{2} - x_{1}} - \sqrt{y_{1} - x_{2}}

即 \sqrt{y_{1} - x_{1}} + \sqrt{y_{2} - x_{2}} \geq \sqrt{y_{2} - x_{1}} + \sqrt{y_{1} - x_{2}}。

两边同时平方得

再化简得

套模板即可。

对于二分队列做法，还存在更优的复杂度。

考虑算法本身的复杂度，其瓶颈在于二分判断一个数开始比另一个数优的位置，而在本题中可以通过解不等式解决。

具体来讲，x 比 y 优的决策点即为满足下列不等式的所有整数 j：（默认只考虑一边）

取 j = \left\lceil {\left( \frac{y - x - t^{2}}{2t} \right)^{2} + y} \right\rceil 即为 x 开始比 y 优的位置，时间复杂度 O(n)。

（可以使用这种方法所有斜率优化题，因为可以使用同样的因式分解证明四边形不等式）

例题 2：诗人小 G（半在线）

小 G 是一个出色的诗人，经常作诗自娱自乐。但是，他一直被一件事情所困扰，那就是诗的排版问题。

一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。

小 G 给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。

显然排版时，不应改变原有的句子顺序，并且一个句子只能在一行内。

在满足上面两个条件的情况下，小 G 对于排版中的每行定义了一个不协调度， 为这行的实际长度与行标准长度差值绝对值的 P 次方，而一个排版的不协调度为所有行不协调度的总和。 请你对几首首诗进行排版，使得排版后的诗不协调度尽量小，并输出排版的结果。

解析：

不协调度只与每个句子的长度有关，所以设每个句子的长度为 l_{1},l_{2},\ldots l_{n}，其前缀和为 s_{1},s_{2},\ldots s_{n}

显然设 f_i 为前 i 个数的最小不协调度，由题可知 w_{x,y} = f_{x} + |\left( s_{y} - s_{x - 1} + y - x \right) - l|^{P}，同样考虑对它证四边形不等式。

:::info[四边形不等式证明]

套进第二个定义的式子，得

两边同时消掉 f_{x} + f_{x + 1} 得：

设 k = s_{y} - s_{x - 1} + y - x - l，k' = k + a_{y + 1} + 1，则原式化为

考虑函数 y = |x|^{P} 的性质，从图像入手。

图像链接，发现函数下凸。

由于 k\lt k'，因此原不等式成立。

（可以使用求导或因式分解的方法证它是下凸的）

套模板即可，注意要求半在线，此外还要注意溢出。

四、四边形不等式（决策单调性）实战 2.0

\ 考虑把状态维数从一维升到二维，但二维 DP 种类较多，需结合题目分析。

以下部分定义 p_{i,j} 表示状态 f_{i,j} 对应的最优决策点。

例题 3：Optimal Binary Search Tree（区间 DP）

\ 求一棵有 N 个节点的二叉搜索树，使 \sum\limits_{i = 1}^{N}{a_{i} \times d_{i}} 最小，其中 a_{i} 为点的权值，d_{i} 为深度（根节点深度为 0）。

（这题是四边形不等式优化 DP 的起源）

解析：设 s_{i} 表示 a_{i} 的前缀和，f_{l,r} 表示区间 [ l,r] 的最小代价。考虑枚举其最优二叉搜索树的根 k，则 f_{l,r} = w_{l,r} + \min\limits_{l \leq k < r}\left ( f_{l,k} + f_{k + 1,r} - a_{k} \right)，其中 w_{l,r} = s_{r} - s_{l - 1}。

这样直接做是 O(n^3) 的，考虑优化，但是二维状态不能省，只能考虑减少枚举 k 次数。

首先考虑证明 f 满足四边形不等式，即对任意 a \leq b \leq c \leq d 有 f_{a,c} + f_{b,d} \leq f_{a,d} + f_{b,c}。

:::info[四边形不等式证明]

设 k_{0} = p_{a,d}，k_{1} = p_{b,c}，分两种情况考虑。

• 若 k_{0} \in [ b,c]

  • &#x20;若 k_{1} \in \left[ a,k_{0} \right] 则&#x20;
  f_{a,d} + f_{b,c} & = f_{a,k_{0}} + f_{k_{0} + 1,d} + f_{b,k_{1}} + f_{k_{1} + 1,c} + w_{a,d} + w_{b,c} - a_{k_{0}} - a_{k_{1}} \\ & \geq f_{a,k_{0}} + f_{k_{1} + 1,c} + f_{b,k_{1}} + f_{k_{0} + 1,d} + w_{a,c} + w_{b,d} - a_{k_{0}} - a_{k_{1}} \end{aligned}

  &#x20;由于无法直接处理，考虑归纳，则有&#x20;

  & f_{a,k_{0}} + f_{k_{1} + 1,c} + f_{b,k_{1}} + f_{k_{0} + 1,d} + w_{a,c} + w_{b,d} - a_{k_{0}} - a_{k_{1}} \\ \geq & f_{a,k_{1}} + f_{k_{1} + 1,c} - a_{k_{1}} + f_{b,k_{0}} + f_{k_{0} + 1,d} + w_{a,c} + w_{b,d} - a_{k_{0}} \\ \geq & f_{a,c} + f_{b,d} \end{aligned}

  &#x20;由于当 a = b 或 c = d 时四边形不等式成立且其他条件下上述论证总会归纳到一个较小的长度，所以归纳成立。\ 此处推导成立要求 w 满足四边形不等式。

  • 若 k_{1} \in \left[ k_{0} + 1,b \right]，方法与上面类似。

• 否则，

在这题中，w 显然满足四边形不等式与区间包含单调性，因此 f 满足四边形不等式。

根据前人的智慧，我们知道 p_{i,j - 1} \leq p_{i,j} \leq p_{i + 1,j}。

先证明 p_{i,j - 1} \leq p_{i,j}。对每一个 i，设 f'_{k,j} = f_{i,k} + f_{k + 1,j} + w_{i,j}，显然 f'_{k,j} 满足四边形不等式，所以对 f_{i,j} = \min\limits_{k = i}^{j}f'_{k,j} 应用一开始的结论即可，证明 p_{i,j} \leq p_{i + 1,j} 的过程类似。

于是可以写出代码如下：

for(int i=1;i<=n;++i)
    p[i][i]=i;
for(int len=2;len<=n;++len)
    for(int l=1,r=len;r<=n;++l,++r){
        for(int k=p[l][r-1];k<=p[l+1][r];++k)
        if(f[l][k]+f[k+1][r]-a[k]<f[l][r])f[l][r]=f[l][k]+f[k+1][r]-a[k],p[l][r]=k;
       f[l][r]+=s[r]-s[l-1];
   }

显然对每一个区间长度的决策量都只有 O(n) 个，因为区间长度共 n 种，因此总时间复杂度 O\left( n^{2} \right)。

可以看出，a_{k} 同样不影响推导过程，可以忽略。

满足四边形不等式的矩阵称为蒙日矩阵，可以类似地在 O(n^2) 时间内计算蒙日矩阵 (\min,+) 乘法。（一般矩阵与蒙日矩阵的 ( \min , +) 乘法也可以直接使用分治优化至 O(n^2\log n)。

例题 4：Yet Another Minimization Problem（多层一维 DP、类莫队）

\ 给定一个长度为 n 的序列 a，要把它分成 k 个子段。每个子段的费用是其中相同元素的对数。求所有子段的费用之和的最小值。

可以直接分治，不考虑计算 w 则时间复杂度 O\left( nk\log n \right)，但是如何计算 w？

显然所有的在线做法都不能做到均摊 O(1)，所以考虑魔改某种离线做法。

根据莫队的知识，如果只需要左右移动区间端点是可以快速求解的，考虑将这种思想用在分治做法上。

在分治到 [l,r]，答案范围为 [L,R]（此处记为分治 [l,r][L,R]）时，需要先对所有 L \leq i \leq \min(\text{mid},R) 计算 w_{i,\text{mid}}。

显然在计算 f_{\text{mid}} 时除了 L 的每个决策点只会移动一次端点，而向左/向右递归时的第一次计算显然只会将两个端点在 [L,R] 内移动一次，所以总移动次数是 O(R-L) 的。

整体时间复杂度仍为 O\left( nk\log n \right)。

计算 w 函数的代码如下，其余与之前没什么区别：

int l0,r0,s[100005];
long long ans;
long long w(int l,int r){
    while(l0>l)--l0,ans+=s[a[l0]],++s[a[l0]];
    while(r0<r)++r0,ans+=s[a[r0]],++s[a[r0]];//注意跟莫队一样先加后减
    while(l0<l)--s[a[l0]],ans-=s[a[l0]],++l0;
    while(r0>r)--s[a[r0]],ans-=s[a[r0]],--r0;
    return ans;
}

特别地，如果使用半在线分治，需要两个莫队分别求 p_{\text{mid},l} 与 p_{r,\text{mid}}，显然第一个莫队的移动次数不多于上面那个，而第二个莫队移动次数的证法和上面完全一致。

这样做是因为由于两个部分的约束分别由决策点和状态点给出，如果只用一个莫队会在 p_1=p_2=\ldots =p_n=1 时爆炸。

例题 5：[IOI2000] 邮局（多层一维 DP）

upd：现在它叫 [IOI2000] 邮局 加强版，因为原题数据范围并没有这么大。

高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。

邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。

你要编写一个程序，已知村庄的位置 x_{1},\ldots x_{n} 和邮局的数量 m，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。

解析：

考虑每个邮局控制的区间 [ i,j]，由小学知识可得将邮局建在 x_{\left\lfloor \frac{i + j}{2} \right\rfloor} 的位置最好。

设 f_{i,j} 表示前 i 个村庄共有 j 个邮局的最小总代价，w_{i,j} 表示一个邮局控制 [ i,j] 时这段区间的最小距离和，s_{i} 表示 x_{i} 的前缀和，{\text{mid}}_{i,j} = \left\lfloor \frac{i + j}{2}\right\rfloor，则有

第一个式子考虑将中点两侧的村庄两两配对，每对村庄的贡献都是后面的减去前面的。

:::info[四边形不等式证明]

之前的那一版不忍直视，重构了一遍。

我们要证的是 \forall 0<x\le y<n,w_{x-1,y+1}+w_{x,y}\ge w_{x-1,y}+w_{x,y+1}，从每个村庄贡献的系数判断。

• (y-x+1)\bmod 2=0

  这种情况下左式比右式多 x_{{\text{mid}_{x,y}}+1}-x_{\text{mid}_{x,y}}。

  例：y-x+1=6 的情况，贡献系数为：

• (y-x+1)\bmod 2=1

  这种情况下左右两式相等。

  例：y-x+1=5 的情况，贡献系数为：

:::

可以继续用分治做，但还有更好的方法。

再次根据前人的智慧，可以知道 p_{i,j - 1} \leq p_{i,j} \leq p_{i + 1,j}。

证明见OI-wiki。

这种方法的代码如下，和区间 dp 十分相似：

for(int j=1;j<=m;++j){
    p[n+1][j]=n;
    for(int i=n;i;--i){//逆序循环是因为要使用p(i+1,j)
        for(int k=p[i][j-1];k<=p[i+1][j];++k)
            if(dp[k][j-1]+w(k+1,i)<dp[i][j])dp[i][j]=dp[k][j-1]+w(k+1,i),p[i][j]=k;
    }
}

与之前类似地，对于任意 i - j 一致的斜线共有 O(n) 次转移，而 i - j 可能有 m + n 种，因此时间复杂度 O\left( n(n + m) \right)。

其实还有更快的办法。

例题 6：[IOI2000] 邮局 加强版（wqs 二分优化）

upd：现在它叫 [IOI 2000] 邮局 加强版 加强版，理由同上。

在此题中，n,m \leq 5 \times 10^{5}。

再再次使用前人的智慧，发现 w_{n,j} 是一个下凸函数，大概长这样：（这个图取自原题目中测试点 2 的数据）

:::info[凸性证明] 要证明凸性，只需证明 f_{n,j - 1} + f_{n,j + 1} \geq 2f_{n,j}。

同样考虑区间分划，将 f_{n,j - 1},f_{n,j},f_{n,j + 1} 对应的区间划分分别设为\

将 a 和 c 在第一个满足 c_{k} \le a_{k-1} 的位置分别拆成两半（因为是第一个所以有 c_k >c_{k-1}> a_{k-2}），交换后半段，形成两个长度为 j 的分划：

大概长这样，其中数字表示分隔点的序号，颜色表示原来的划分：

对 a_{k - 2},c_{k},a_{k - 1} - 1,c_{k + 1} - 1 应用四边形不等式，得交换后两个分划的代价和不低于原来的代价和，又因为最优性于是有 f_{n,j-1}+f_{n,j+1}\ge 2f_{n,j}。

知道凸性之后，就可以用 wqs 二分解决了。

为了方便，使用原题目中的样例进行演示，它的图像长这样（由于点 (1,117) 过高不放出）：

由于斜率具有单调性，考虑二分斜率。

当枚举到一个斜率 k 时，根据每个点 \left( j,f_{n,j} \right) 与斜率 k 作直线，如当 k = - 5 时长这样：

图像链接

可以发现，当且仅当一个点作出的直线是最下面的那条（也就是这个点是切点），连接这个点的两条线段的斜率 k_{1},k_{2} 满足 k_{1} \leq k \leq k_{2}。

考虑如何快速计算最下面的那条直线，从截距 b = f_{n,j} - j \times k 入手，b 最小的直线即为所求。

可以发现，要计算这个东西只要将价值函数设为 w'_{i,j} = w_{i,j} - k，然后不考虑选多少个，令 f'_i 为前 i 个数对应的最小截距（f'_{i} = \min\limits_{k \leq i}\left( f'_{k} + w'_{k,i} \right)），利用前面的方法求出 f'_i 最小值，再在过程中记录对应的划分段数 x 即可。

注意答案对应的斜率可能会对应多个段数（即形成平台），比如当 k = 6 时会出现这种情况：

因此，在转移时，要注意只能取到平台的一端（也就是最小答案对应的最小 / 最大划分段数），同时注意最终答案是 b+mk 而不是 b+xk。

为什么取 b+mk 是对的：因为 m 和 x 对应的 k 相同，并且求出了正确的 b。

容易发现它不能输出正确方案，可能可以通过微调的方式避免平台从而输出正确方案，但我也不知道怎么微调。

各种写法的代码如下：

:::info[二分队列写法 1（取平台左侧）]

void solve(){
    deque<int> q;
    l[0]=1,r[0]=n;
    q.push_back(0);
    for(int i=1;i<=n;++i){
        while(!q.empty()&&i>r[q.front()])q.pop_front();
        dp[i]=w(q.front(),i)-Mid,cnt[i]=cnt[q.front()]+1;
        while(!q.empty()&&w(q.back(),l[q.back()])>=w(i,l[q.back()]))
            q.pop_back();
        if(q.empty()){
            q.push_back(i);
            l[i]=i+1,r[i]=n;
        }
        else if(w(q.back(),r[q.back()])<=w(i,r[q.back()])){
                if(r[q.back()]<n){
                    q.push_back(i);
                    l[i]=r[q.back()]+1,r[i]=n;
                }
            }
            else{
                int L=l[q.back()],R=r[q.back()],mid,p;
                while(R>=L){
                    mid=(R+L)/2;
                    if(w(q.back(),mid)>=w(i,mid))p=mid,R=mid-1;
                    else L=mid+1;
                }
                r[q.back()]=p-1,l[i]=p,r[i]=n;
                q.push_back(i);
            }
      }
}
//主函数内二分部分
long long ans,L=-1e14,R=0;
while(R>=L){
    Mid=(L+R)/2;
    solve();
    if(cnt[n]<=m)ans=dp[n]+m*Mid,L=Mid+1;//当最大点在n左侧时统计答案
    else R=Mid-1;
}

:::

:::info[二分队列写法 2（取平台右侧）]

void solve(){
    deque<int> q;
    l[0]=1,r[0]=n;
    q.push_back(0);
    for(int i=1;i<=n;++i){
        while(!q.empty()&&i>r[q.front()])q.pop_front();
        dp[i]=w(q.front(),i)-Mid,cnt[i]=cnt[q.front()]+1;
        while(!q.empty()&&w(q.back(),l[q.back()])>w(i,l[q.back()]))//这里变了
            q.pop_back();
        if(q.empty()){
            q.push_back(i);
            l[i]=i+1,r[i]=n;
        }
        else if(w(q.back(),r[q.back()])<w(i,r[q.back()])){//这里变了
                if(r[q.back()]<n){
                    q.push_back(i);
                    l[i]=r[q.back()]+1,r[i]=n;
                }
            }
            else{
                int L=l[q.back()],R=r[q.back()],mid,p;
                while(R>=L){
                    mid=(R+L)/2;
                    if(w(q.back(),mid)>w(i,mid))p=mid,R=mid-1;//这里变了
                    else L=mid+1;
                }
                r[q.back()]=p-1,l[i]=p,r[i]=n;
                q.push_back(i);
            }
      }
}
//主函数内二分部分
long long ans,L=-1e14,R=0;
while(R>=L){
    Mid=(L+R)/2;
    solve();
    if(cnt[n]<m)L=Mid+1;
    else ans=dp[n]+m*Mid,R=Mid-1;//当最大点在n右侧时统计答案
}

:::

:::info[半在线分治的写法（以取平台左侧为例，二分写法相同就不放了）]

void solve(int l,int r){
    if(r==l+1)return;
    int mid=(l+r)>>1;
    p[mid]=p[l],dp[mid]=w(p[mid],mid),cnt[mid]=cnt[p[mid]]+1;
    for(int i=p[l]+1;i<=p[r];++i)
        if(w(i,mid)<dp[mid]||(w(i,mid)==dp[mid]&&cnt[i]+1<cnt[mid]))dp[mid]=w(i,mid),p[mid]=i,cnt[mid]=cnt[i]+1;
    solve(l,mid);
    for(int i=l+1;i<=mid;++i)
        if(w(i,r)<dp[r]||(w(i,r)==dp[r]&&cnt[i]+1<cnt[r]))dp[r]=w(i,r),p[r]=i,cnt[r]=cnt[i]+1;
    solve(mid,r);
}

:::

习题：

当你发现转移式中含有区间最值和一些凸函数的组合时，就可以考虑四边形不等式了。

• 一维 DP

Yakiniku Restaurants\ [HNOI2008] 玩具装箱\ Max (Sum - Max)\ [COCI 2023/2024 #5] Rolete\ 「雅礼集训 2017 Day5」珠宝 /「NAIPC2016」Jewel Thief

• 二维 DP

  • 区间 DP

  [NOI1995] 石子合并\ [IOI1998] Polygon

  • 区间拆分

  Ciel and Gondolas\ [CmdOI2019] 任务分配问题\ 忘情

• 所有（？的单调队列 / 斜率优化题目