四边形不等式优化

四边形不等式优化利用的是状态转移方程中的决策单调性，也常称为 决策单调性优化 DP。

基础知识

考虑最简单的情形，我们要解决如下一系列最优化问题：

$$\begin{array}{}\text{(1)}& f(i)=\underset{1\le j\le i}{min}w(j,i)(1\le i\le n)\end{array}$$

这里假定成本函数 $w(j,i)$ 可以在 $O(1)$ 时间内计算。

在一般的情形下，这些问题总时间复杂度为 $O(n^2)$。这是由于对于问题 $i$，我们需要考虑所有可能的决策 $j$。而在满足决策单调性时，可以有效缩小决策空间，优化总复杂度。

• 决策单调性：对于任意 ，必然成立 $\mathrm{opt}(i_1)\le \mathrm{opt}(i_2)$。

最常见的判断决策单调性的方法是通过四边形不等式（quadrangle inequality）。在不同的语境下，这一性质也常称为 Monge 性质（用于描述矩阵 $A_{j,i}$）或次模性（submodularity，用于描述以区间为自变量的函数 $f([j,i])$）。

• 四边形不等式：如果对于任意 $a\le b\le c\le d$ 均成立

  $$w(a,c)+w(b,d)\le w(a,d)+w(b,c),$$

  则称函数 $w$ 满足四边形不等式（简记为「交叉小于包含」）。若等号永远成立，则称函数 $w$ 满足 四边形恒等式。

如果没有特别说明，以下都会保证 $a\le b\le c\le d$。四边形不等式给出了一个决策单调性的充分不必要条件。

四边形不等式可以理解在合理的定义域内，$w$ 的二阶混合差分 ${\mathrm{\Delta }}_i{\mathrm{\Delta }}_{j}w(j,i)$ 非正。

利用决策单调性，有很多常见算法都可以将算法复杂度优化到 $O(n\log n)$。这些算法的适用范围、实现难度、运行效率各不相同，需要根据实际场景选择合适的算法。这主要取决于 $w(j,i)$ 的性质。不加说明时，本文默认 $w(i,j)$ 可以 随机访问，即 $w(j,i)$ 可以在 $O(1)$ 时间内查询或计算。但是，并非所有问题中，$w(j,i)$ 都这样容易计算。因此，除了基本情形外，本文还讨论了 $w(j,i)$ 只具有如下性质时，利用决策单调性优化 DP 的方法：

• 移动访问：$w(j,i)$ 可以从 $w(j\pm 1,i)$ 或 $w(j,i\pm 1)$ 以 $O(1)$ 时间转移得到。（类似 莫队算法 中的情形）
• 动态计算：$w(j,i)$ 的计算依赖于 。这意味着 $f$ 和 $w$ 只能顺次计算。下文介绍了不限制区间个数的区间分拆问题，它就属于这一情形。

这两条性质并不互斥，可能存在 $w(j,i)$ 既需要动态计算，又只支持移动访问的情形。

分治

要求解所有状态，只需要求解所有最优决策点。为了对所有 $1\le i\le n$ 求解 $\mathrm{opt}(i)$，首先计算 $\mathrm{opt}(n/2)$，而后分别计算 和 上的 $\mathrm{opt}(i)$，注意此时已知前半段的 $\mathrm{opt}(i)$ 必然位于 $1$ 和 $\mathrm{opt}(n/2)$ 之间（含端点），而后半段的 $\mathrm{opt}(i)$ 必然位于 $\mathrm{opt}(n/2)$ 和 $n$ 之间（含端点）。对于两个子区间，也类似处理，直至计算出每个问题的最优决策。在分治的过程中记录搜索的上下边界，就可以保证算法复杂度控制在 $O(n\log n)$。递归树层数为 $O(\log n)$，而每层中，单个决策点至多计算两次，所以总的计算次数是 $O(n\log n)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

val_t w(int j, int i);  // 成本函数
val_t f[N];             // 最优值
int opt[N];             // 最小最优决策

// 递归求解 [l,r] 中的问题
// 已知它们的最小最优决策点一定出现在区间 [opt_l, opt_r] 中
void calc(int l, int r, int opt_l, int opt_r) {
  int mid = (l + r) / 2;
  // 求问题 mid 的最优决策点
  for (int j = opt_l; j <= std::min(opt_r, mid); ++j) {
    if (w(j, mid) < f[mid]) {
      f[mid] = w(j, mid);
      opt[mid] = j;
    }
  }
  // 根据决策单调性得出左右两部分的决策区间，递归处理
  if (l < mid) calc(l, mid - 1, opt_l, opt[mid]);
  if (r > mid) calc(mid + 1, r, opt[mid], opt_r);
}

// 求解整个区间 [1,n] 的问题
void solve(int n) {
  // 每次调用递归函数前，都需要清空数组 f
  std::fill(f + 1, f + n + 1, inf);
  // 最开始时，只知道问题 [1,n] 的所有决策点都一定在 [1,n] 中
  calc(1, n, 1, n);
}

除了随机访问的基本情形外，分治算法还可以应用于 $w(j,i)$ 只支持移动访问的情形。只需要在计算过程中维护游标 $(j,i)$ 和相应函数值 $w(j,i)$，在需要查询新的值时，将游标暴力移动到当前位置并更新函数值即可。这样做的时间复杂度仍然为 $O(n\log n)$。对此更为详细的讨论，可以参考下文 简化 LARSCH 算法 一节。但是，分治算法无法解决 $w(j,i)$ 需要动态计算的情形，因为分治算法没有办法在左半区间问题尚未解决时，就计算出区间中点处的最小最优决策 $\mathrm{opt}(n/2)$。

二分队列

注意到对于每个决策点 $j$，能使其成为最小最优决策点的问题 $i$ 必然构成一个区间。可以通过单调队列记录到目前为止每个决策点可以解决的问题的区间，这样，问题的最优解自然可以通过队列中记录的决策点计算得到。

具体地，算法需要顺次遍历决策点。当遍历到决策点 $k$ 时，队列中需要记录到目前为止每个可行的决策点 $j$ 和能够解决的问题区间左右端点 $l_j$ 和 $r_j$ 构成的 三元组。对于给定区间 $[l_j,r_j]$ 内的问题，$j$ 应该是到目前为止考虑过的决策点（即区间 $[1,k]$ 中的决策点）中最小最优的。每时每刻，队列中存储的决策未必是连续的，但是尚未解决的问题 $[j,n]$ 应该是队列中存储的问题区间的不交并。

为了说明队列更新过程中，决策点 $j$ 是最小最优决策的问题 $i$ 总构成一段连续的区间，需要适当加强前文的结论：

该算法过程如下：¹

• 初始时，队列是空的。类似于单调队列，每次考虑下一个决策 $j$ 的时候，都需要进行出队和入队操作。
• 出队：首先将上一个问题 $j-1$ 从队列中移除。如果队首的决策能够解决的问题的右端点恰为 $j-1$，直接弹出队首；否则，将队首决策能够解决问题的左端点更新为 $j$。
• 入队：要对决策 $j$ 进行入队时，首先比较它和队尾的决策 $j^{\prime }$。
  • 如果对于问题 $l_{j^{\prime }}$，将要入队的决策 $j$ 比已有的决策 $j^{\prime }$ 严格更优，即 时，则弹出队尾的决策 $j^{\prime }$。此操作持续到队列为空或队尾的决策 $j^{\prime }$ 比起 $j$ 对于问题 $l_{j^{\prime }}$ 更优时为止。
  • 如果队列已空，入队 $(j,j,n)$，即认为决策 $j$ 是尚未解决的所有问题的最优解。
  • 如果队尾决策 $j^{\prime }$ 对于问题 $r_{j^{\prime }}$ 同样不劣于将入队的决策 $j$，那么当 时，入队 $(j,r_{j^{\prime }}+1,n)$，表示 $j$ 是问题 $[r_{j^{\prime }}+1,n]$ 的最小最优决策；否则，不需要入队 $j$，因为它并不比已有的决策更优。
  • 最后的情形是，队尾决策 $j^{\prime }$ 比起要入队的决策 $j$ 对于问题 $l_{j^{\prime }}$ 严格更优，而对于问题 $r_{j^{\prime }}$ 严格更劣。这说明，存在问题 $i\in (l_{j^{\prime }},r_{j^{\prime }}]$ 使得问题 $[l_{j^{\prime }},i-1]$ 的最小最优决策为 $j^{\prime }$ 且问题 $[i,r_{j^{\prime }}]$ 的最小最优决策为 $j$。因而，需要通过 二分 找到最小的 $i\in [l_{j^{\prime }},r_{j^{\prime }}]$ 使得 ，再将队尾的区间右端点 $r_{j^{\prime }}$ 修改为 $i-1$，并入队 $(j,i,n)$。
• 处理完决策 $j$ 后，就已经处理了所有到 $j$ 为止的决策。此时，队首决策就是问题 $j$ 的最小最优决策，可以记录相应的最优解。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

val_t w(int j, int i);  // 成本函数
val_t f[N];             // 最优值
int opt[N];             // 最小最优决策
int lt[N], rt[N];       // 决策 j 可以解决的问题区间 [l_j,r_j]

// 求解整个区间 [1,n] 的问题
void solve(int n) {
  std::deque<int> dq;  // 存储所有可行决策的单调队列

  // 顺次考虑所有问题和决策，下标从 1 开始
  for (int j = 1; j <= n; ++j) {
    // 出队
    if (!dq.empty() && rt[dq.front()] < j) dq.pop_front();
    if (!dq.empty()) lt[dq.front()] = j;
    // 入队
    while (!dq.empty() && w(j, lt[dq.back()]) < w(dq.back(), lt[dq.back()])) {
      dq.pop_back();
    }
    if (dq.empty()) {
      lt[j] = j;
      rt[j] = n;
      dq.emplace_back(j);
    } else if (w(j, rt[dq.back()]) >= w(dq.back(), rt[dq.back()])) {
      if (rt[dq.back()] < n) {
        lt[j] = rt[dq.back()] + 1;
        rt[j] = n;
        dq.emplace_back(j);
      }
    } else {
      int ll = lt[dq.back()], rr = rt[dq.back()], i = rr;
      // 二分
      while (ll <= rr) {
        int mm = (ll + rr) / 2;
        if (w(j, mm) < w(dq.back(), mm)) {
          i = mm;
          rr = mm - 1;
        } else {
          ll = mm + 1;
        }
      }
      rt[dq.back()] = i - 1;
      lt[j] = i;
      rt[j] = n;
      dq.emplace_back(j);
    }
    // 计算
    f[j] = w(dq.front(), j);
    opt[j] = dq.front();
  }
}

类似于单调队列，每个决策点至多入队一次，出队一次。其中，出队是 $O(1)$ 的，而入队是 $O(\log n)$ 的（可能需要二分），所以总的时间复杂度是 $O(n\log n)$。

由于二分队列算法顺次考虑所有问题和决策点，它可以应用于 $w(j,i)$ 需要动态计算的情形。这是它相较于分治算法的优势。但是，因为算法中的二分步骤依赖于对 $w(j,i)$ 的随机访问，它无法应用于 $w(j,i)$ 只支持移动访问的情形。

例题 1：「POI2011」Lightning Conductor

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots ,a_n$，要求对于每一个 $1\le i\le n$，找到最小的非负整数 $f_i$ 满足

$$\mathrm{\forall }j\in [1,n]:a_j\le a_i+f_i-\sqrt{|i-j|}.$$

思路

显然，经过不等式变形，我们可以得到待求整数 $f_i=\underset{j}{max}\{a_j+\sqrt{|i-j|}-a_i\}$。不妨先考虑 $j\le i$ 的情况（另外一种情况类似），此时我们可以得到状态转移方程：

$$f_i=-\underset{j\le i}{min}\{-a_j-\sqrt{i-j}+a_i\}.$$

根据 $-\sqrt{x}$ 的凸性，我们很容易得出（后文将详细描述）函数 $w(l,r)=-a_l-\sqrt{r-l}+a_r$ 满足四边形不等式，因此套用上述的算法便可在 $O(n\log n)$ 的时间内解决此题了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#define all \
  for (auto i : {&q, &l, &r}) (*i)
using namespace std;
int n, a[500009], ans[500009];
deque<int> q, l, r;

double f(int i, int j) { return a[i] + sqrtl(j - i); }

void work() {
  all.clear();
  for (int i = 0; i < n; ++i) {
    if (q.size() && r.front() < i) all.pop_front();  // 队首出队
    if (q.size()) l.front() = i;
    for (; q.size() && f(q.back(), l.back()) <= f(i, l.back());)  // 队尾出队
      all.pop_back();
    if (q.empty())  // 入队
      q.emplace_back(i), l.emplace_back(i), r.emplace_back(n);
    else if (f(q.back(), n) < f(i, n)) {
      int ll = l.back(), rr = n, mid;
      for (; ll <= rr;) {
        mid = (ll + rr) >> 1;
        if (f(q.back(), mid) < f(i, mid))
          rr = mid - 1;
        else
          ll = mid + 1;
      }
      r.back() = rr;
      q.emplace_back(i), l.emplace_back(ll), r.emplace_back(n);
    }
    ans[i] = max(ans[i], (int)(ceil(f(q.front(), i))) - a[i]);
  }
}

int main() {
  cin >> n;
  for (int i = 0; i < n; cin >> a[i++]);
  work();
  reverse(a, a + n);
  reverse(ans, ans + n);
  work();
  reverse(ans, ans + n);
  for (int i = 0; i < n; cout << ans[i++] << '\n');
}

简化 LARSCH 算法

前两种算法都无法处理 $w(j,i)$ 既需要动态计算，也只支持移动访问的情形。本节介绍一种能够同时克服这两种困难的算法。它是 Larmore 和 Schieber 在 1991 年提出的 LARSCH 算法²的简化版本，故称为 简化 LARSCH 算法。该算法的原始版本可以在 $O(n)$ 时间内解决决策单调性 DP 问题，但实现较复杂，本文不做介绍。

仍然考虑分治求解。求解区间 $(l,r]$ 内的问题时，假设如下信息已知：

• 区间 $[1,l]$ 中问题 $i$ 的最小最优决策 $\mathrm{opt}(i)$ 和最优值，以及
• 仅考虑区间 $[1,l]$ 中的决策，问题 $r$ 的最小最优决策 ${\mathrm{opt}}_l(r)$ 和最优值。

区间 $(l,r]$ 内的问题求解结束时，需要得到区间 $(l,r]$ 内问题的最小最优决策和最优值。

设 $\mathit{\text{mid}}$ 为区间 $(l,r]$ 的中点。求解过程如下：

1. 遍历决策 $i\in [\mathrm{opt}(l),{\mathrm{opt}}_l(r)]$，更新问题 $\mathit{\text{mid}}$ 的最小最优决策和最优值。
2. 递归求解区间 $(l,\mathit{\text{mid}}]$ 中的问题。
3. 遍历决策 $i\in (l,\mathit{\text{mid}}]$，更新问题 $r$ 的最小最优决策和最优值。
4. 递归求解区间 $(\mathit{\text{mid}},r]$ 中的问题。

对整个区间 $[1,n]$ 执行递归前，首先需要用决策 $j=1$ 更新问题 $i\in \{1,n\}$。该算法在递归到 $l=r$ 时就终止。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

val_t w(int j, int i);  // 成本函数
val_t f[N];             // 最优值
int opt[N];             // 最小最优决策

// 用决策 j 更新问题 i
void check(int j, int i) {
  if (w(j, i) < f[i]) {
    f[i] = w(j, i);
    opt[i] = j;
  }
}

// 递归求解区间 (l, r] 内的问题
void calc(int l, int r) {
  int mid = (l + r + 1) / 2;
  for (int j = opt[l]; j <= opt[r]; ++j) check(j, mid);
  if (mid < r) calc(l, mid);
  for (int j = l + 1; j <= mid; ++j) check(j, r);
  if (mid > l) calc(mid, r);
}

// 求解整个区间 [1, n] 内的问题
void solve(int n) {
  // 清空 f 数组
  std::fill(f + 1, f + n + 1, inf);
  // 初始化
  check(1, 1);
  check(1, n);
  // 递归求解区间 (1, n] 内的问题
  calc(1, n);
}

首先，可以说明这一算法的正确性。为此，只要检查每一递归求解的步骤（即步骤 2 和 4）前都满足上文给出的前提条件。由前一节得到的推论 1，有 $\mathrm{opt}(l)={\mathrm{opt}}_l(l)\le {\mathrm{opt}}_l(\mathit{\text{mid}})\le {\mathrm{opt}}_l(r)$，所以步骤 1 后，${\mathrm{opt}}_l(\mathit{\text{mid}})$ 是已知的，进而执行步骤 2 前递归求解区间 $(l,\mathit{\text{mid}}]$ 中问题的前提条件成立。由于之前 $\{\mathrm{opt}(i):i\in [1,l]\}$ 是已知的，步骤 2 又得到了 $\{\mathrm{opt}(i):i\in (l,\mathit{\text{mid}}]\}$ 的取值，所以这之后 $\{\mathrm{opt}(i):i\in [1,\mathit{\text{mid}}]\}$ 都是已知的；同时，由于之前 ${\mathrm{opt}}_l(r)$ 是已知的，步骤 3 后，${\mathrm{opt}}_{\mathit{\text{mid}}}(r)$ 就也是已知的。因此，执行步骤 4 前递归求解区间 $(\mathit{\text{mid}},r]$ 中问题的前提条件也成立。

然后，需要说明该算法的复杂度仍然是 $O(n\log n)$ 的。递归树的层数是 $O(\log n)$ 的。对于递归树中的同一层的每个结点，分别遍历区间 $[\mathrm{opt}(l),{\mathrm{opt}}_l(r)]$ 和 $(l,\mathit{\text{mid}}]$ 中的决策。因为 $\mathrm{opt}(l)\le {\mathrm{opt}}_l(r)\le \mathrm{opt}(r)$，所以在同一层中，每个决策点只遍历了 $O(1)$ 次。故而，递归树的每一层中总的遍历次数是 $O(n)$ 的。假设单次访问或计算 $w(j,i)$ 的复杂度是 $O(1)$ 的，算法的时间复杂度就是 $O(n\log n)$ 的。

对于一些 $w(j,i)$ 只支持移动访问的情形，这一算法的复杂度仍然是 $O(n\log n)$ 的。此时，需要为算法流程中的步骤 1 和步骤 3 分别维护游标 $(j,i)$ 和 $w(j,i)$ 的当前取值。每次需要访问新的值时，需要将游标 $(j,i)$ 从上一次访问时的位置暴力更新到当前位置，并对函数值 $w(j,i)$ 进行转移。容易验证，当对递归树进行遍历时，这些暴力更新的总次数是 $O(n\log n)$ 的。所以，算法的时间复杂度仍然是 $O(n\log n)$ 的。

非随机访问的复杂度证明

只需要证明游标移动的总次数是 $O(n\log n)$ 的。设 $A$ 和 $B$ 分别为步骤 1 和 3 对应的游标。实际上可以保证：在求解区间 $(l,r]$ 的问题之前，游标 $A$ 处于位置 $(\mathrm{opt}(l),l)$，游标 $B$ 处于位置 $(l,l)$；而在这之后，游标 $A$ 处于位置 $(\mathrm{opt}(r),r)$，游标 $B$ 处于位置 $(r,r)$。

考虑构造如下游标移动规则。步骤 1 中，可以令游标 $A$ 沿着路径

$$(\mathrm{opt}(l),l)\to (\mathrm{opt}(l),\mathit{\text{mid}})\to ({\mathrm{opt}}_l(r),\mathit{\text{mid}})\to (\mathrm{opt}(l),\mathit{\text{mid}})\to (\mathrm{opt}(l),l)$$

移动。此时，游标 $A$ 和 $B$ 均处于求解区间 $(l,\mathit{\text{mid}}]$ 的问题之前的规定位置上。步骤 2 中，按规定，游标 $A$ 将移动到 $(\mathrm{opt}(\mathit{\text{mid}}),\mathit{\text{mid}})$，游标 $B$ 将移动到 $(\mathit{\text{mid}},\mathit{\text{mid}})$。步骤 3 中，可以令游标 $B$ 沿着路径

$$(\mathit{\text{mid}},\mathit{\text{mid}})\to (l,\mathit{\text{mid}})\to (l,r)\to (\mathit{\text{mid}},r)\to (\mathit{\text{mid}},\mathit{\text{mid}})$$

移动。此时，游标 $A$ 和 $B$ 均处于求解区间 $(\mathit{\text{mid}},r]$ 的问题之前的规定位置上。步骤 4 中，按规定，游标 $A$ 将移动到 $(\mathrm{opt}(r),r)$，游标 $B$ 将移动到 $(r,r)$。两个游标均在结束求解区间 $(l,r]$ 的问题的规定位置上。因此，这一移动规则符合上述规定。而且，该移动规则足以完成步骤 1 和 3 中的所有计算。直接计算该规则中游标的移动次数可知，步骤 1 需要

$$2({\mathrm{opt}}_l(r)-\mathrm{opt}(l))+2(\mathit{\text{mid}}-l)$$

次移动，步骤 3 需要

$$2(\mathit{\text{mid}}-l)+2(r-\mathit{\text{mid}})=2(r-l)$$

次移动。将这些移动次数对递归树中的所有结点求和，利用同一层中的所有 $[l,r]$ 和 $[\mathrm{opt}(l),{\mathrm{opt}}_l(r)]$ 至多只在端点处重合这一性质，就可以说明总的移动次数是 $O(n\log n)$ 的。

由于上述移动规则比起实际计算时游标的移动设置了更多的途径点，所以游标的实际移动次数不会超过该规则下移动次数的估计。因此，游标的实际移动次数也是 $O(n\log n)$ 的。

由于该算法在求解区间 $(l,r]$ 的问题前，已经计算出了区间 $[1,l]$ 中的最优解 $f(i)$，所以该算法也可以应用于 $w(j,i)$ 需要动态计算的情形。

区间分拆问题

考虑将某个区间拆分成若干个子区间的问题。形式化地说，将给定区间 $[1,n]$ 拆分成 $[a_1,b_1],\cdots ,[a_k,b_k]$，其中，$a_1=1$，$b_k=n$，以及 $b_i+1=a_{i+1}$ 对任意 都成立。对于给定拆分，成本为 $\sum _{i=1}^{k}w(a_i,b_i)$。问题要求最小化这一成本。可以列出如下的 1D1D 状态转移方程。

$$f(i)=\underset{1\le j\le i}{min}f(j-1)+w(j,i)(1\le i\le n)$$

这里，$f(0)=0$。注意到，只要 $w(j,i)$ 满足四边形不等式，$f(j-1)+w(j,i)$ 必然满足四边形不等式，因为第一项并不包括 $j$ 和 $i$ 的交叉项，在混合差分时会消去。但是由于成本函数依赖于前面的子问题，这一转移只能够顺序计算，所以无法应用前文描述的第一种分治算法，通常只适合应用二分队列算法或简化 LARSCH 算法。算法复杂度为 $O(n\log n)$。

限制区间个数的情形

上述问题可以加强为限制区间个数的情形，即问题指定将区间拆分成 $m$ 个子区间。此时需要将拆分后的区间个数作为转移状态的一维。相应地，有 2D1D 状态转移方程如下。

$$\begin{array}{}\text{(2)}& f(k,i)=\underset{1\le j\le i}{min}f(k-1,j-1)+w(j,i)(1\le k\le m,1\le i\le n)\end{array}$$

这里，$f(0,0)=0$，$f(0,i)=f(k,0)=\mathrm{\infty }$ 对任意 $1\le k\le m$ 和 $1\le i\le n$ 都成立。和上文同样的道理，这里的 $f(k-1,j-1)+w(j,i)$ 必然满足四边形不等式。此时对于第 $i$ 层的计算，并不再依赖于该层的结果，所以对于每一层，都可以通过上一节描述的任何算法进行计算，此时算法复杂度为 $O(mn\log n)$。

对于这一问题，利用决策单调性，实际上还存在其他的优化算法。第二种优化思路依赖于如下结果。这种优化算法和下文详细描述的 Knuth 优化算法十分相似。

证明

第二个不等式只是第 $k$ 层的决策单调性。关键在于第一个不等式。

下证 $\mathrm{opt}(k,i)\le \mathrm{opt}(k+1,i)$。假设有如下两个区间 $[1,i]$ 的分划（逆序标号）：$[a_k,d_k],\cdots ,[a_1,d_1]$ 和 $[b_{k+1},c_{k+1}],\cdots ,[b_1,c_1]$。其中，每个区间的左端点都是其右端点处对应问题的最小最优决策；同样地，从右向左考虑所有可能的分划，右端点也是左端点对应问题的最小最优决策。例如，$d_j$ 和 $c_j$ 分别是将 $[a_j,i]$ 和 $[b_j,i]$ 分成 $j$ 段左起第一个区间右端点的最小最优决策。根据决策单调性，如果 ，亦即 ，那么必然有 。由此，如果所证不成立，则有 。进而可以归纳地证明 。这显然与所设矛盾。由此得证。

第一个不等式可以另证如下。同样考虑上面证明中的两个分划。如果所证命题不成立，则有 ，但是由于有 ，我们可以找到最小的 使得 $a_j\le b_j$。进而，此时有 ，故 。我们找到了一组区间满足 。考虑将这两个分拆重新组合的结果。考虑分拆 $[b_{k+1},c_{k+1}],\cdots ,[b_{j+1},c_{j+1}],[b_j,d_j],[a_{j-1},d_{j-1}],\cdots ,[a_1,d_1]$，共 $(k+1)$ 段，于是由前设的最优性可推知，

同样地，考虑分拆 $[a_k,d_k],\cdots ,[a_{j+1},d_{j+1}],[a_j,c_j],[b_{j-1},c_{j-1}],\cdots ,[b_1,c_1]$，共 $k$ 段，则有

此时，不等号是严格的，因为 ，但是按假设，$a_1$ 是所有 $k$ 段分拆最末一段的左端点中最小最优的。两个不等式条件相加，得到 ，这有悖于四边形不等式。故而原结论得证。

利用这一结果，我们可以限制决策 $j$ 的搜索范围。算法实现时，对 $k$ 正向遍历，对 $i$ 逆向遍历，在之前已确定的上下界范围内暴力搜索 $j$ 就可以保证 $O(n(n+m))$ 的算法复杂度。

最后一种优化方法来源于如下的观察。

证明

下证 $g(k-1)+g(k+1)\ge 2g(k)$。为此，考虑长度为 $(k-1)$ 段和 $(k+1)$ 段的最优分划，分别是 $[a_1,d_1],\cdots ,[a_{k-1},d_{k-1}]$ 和 $[b_1,c_1],\cdots ,[b_{k+1},c_{k+1}]$。取最小的 $1\le j\le k-1$ 使得 $c_{j+1}\le d_j$，其存在性可由 推知。根据其最小性得知，。所以，。与上文类似，交换两个现有分拆的后半段，可以得到如下两个区间分拆：

两个所得区间都是 $k$ 段的，所以由最优性条件可知

这里第二个不等式正是四边形不等式。所求凸性由此得证。

这一结论保证了可以通过 WQS 二分（国外称 Aliens Trick）的方法解决此问题。具体来说，考虑带参的成本函数 $w_c(j,i):=w(j,i)+c$，解决不限制区间个数的问题，求得其最优解为 $f_c(n)$。随着实数 $c$ 递增，相应的最优区间的数目单调递减，故而可以通过二分的方法找到恰使得最优区间个数等于 $m$ 的参数 $c$，则原题最优解为 $f(n,m)=f_c(n)-cm$。这里的实数 $c$ 可以看作区间个数限制的 Lagrange 乘子。该算法的实现有很多细节，可以参考 WQS 二分 页面。这一算法的时间复杂度为 $O(n\log n\log C)$，这里 $C$ 为某一常数。

对于限制区间个数的区间分拆问题的三种算法，在不同的数据范围时表现各有优劣，需要结合具体的题目选择合适的算法。

实现 1，前文第二种优化，复杂度 $O(n(n+m))$

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include <iostream> constexpr int N = 3009; constexpr int M = 309; using namespace std; int n, m, a[N], s[N], g[M][N], p[M][N]; int f(int i, int j) { int k = (i + j) >> 1; return a[k] * (k - i + 1) - (s[k] - s[i - 1]) + (s[j] - s[k]) - a[k] * (j - k); } int main() { cin >> n >> m; for (int i = 1; i <= n; cin >> a[i], s[i] = s[i - 1] + a[i], ++i); for (int i = 1; i <= n; ++i) g[0][i] = 1 << 30, p[m + 1][i] = i; for (int i = 1; i <= m; ++i) p[i][0] = 1; for (int i = 1; i <= n; ++i) for (int j = m; j; --j) { g[j][i] = 1 << 30; for (int k = p[j][i - 1]; k <= p[j + 1][i]; ++k) { int tmp = g[j - 1][k - 1] + f(k, i); if (tmp < g[j][i]) g[j][i] = tmp, p[j][i] = k; } } cout << g[m][n]; }

实现 2，WQS 二分，复杂度 $O(n\log n\log C)$

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

#include <deque> #include <iostream> #define all \ for (auto i : {&q, &l, &r}) (*i) using namespace std; long long n, m, a[500009], s[500009], u, v, w, sum[500009], cnt[500009]; deque<int> q, l, r; long long f(int i, int j) { int k = (i + j) >> 1; return sum[i - 1] + v + a[k] * (k - i + 1) - (s[k] - s[i - 1]) + (s[j] - s[k]) - a[k] * (j - k); } void work() { all.clear(); for (int i = 1; i <= n; ++i) { if (q.size() && r.front() < i) all.pop_front(); // 队首出队 if (q.size()) l.front() = i; for (; q.size() && f(q.back(), l.back()) >= f(i, l.back());) // 队尾出队 all.pop_back(); if (q.empty()) // 入队 q.emplace_back(i), l.emplace_back(i), r.emplace_back((int)n); else if (f(q.back(), n) >= f(i, n)) { int ll = l.back(), rr = n, mid; for (; ll <= rr;) { mid = (ll + rr) >> 1; if (f(q.back(), mid) >= f(i, mid)) rr = mid - 1; else ll = mid + 1; } r.back() = rr; q.emplace_back(i), l.emplace_back(ll), r.emplace_back((int)n); } sum[i] = f(q.front(), i); cnt[i] = cnt[q.front() - 1] + 1; } } int main() { cin >> n >> m; for (int i = 1; i <= n; cin >> a[i], s[i] = s[i - 1] + a[i], ++i); for (w = 2e12; u <= w;) { // wqs二分 v = (u + w) >> 1; work(); if (cnt[n] < m) w = v - 1; else u = v + 1; } v = w; work(); cout << sum[n] - m * v; }