四边形不等式优化

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

基础知识

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

这里假定成本函数 可以在 时间内计算。

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

• 决策单调性：对于任意 ，必然成立 。

最常见的判断决策单调性的方法是通过四边形不等式（quadrangle inequality）。

• 四边形不等式：如果对于任意 均成立

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

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

四边形不等式可以理解在合理的定义域内， 的二阶混合差分 非正。

利用决策单调性，有两种常见算法可以将算法复杂度优化到 。

分治

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int w(int j, int i);

void DP(int l, int r, int k_l, int k_r) {
  int mid = (l + r) / 2, k = k_l;
  // 求状态f[mid]的最优决策点
  for (int j = k_l; j <= min(k_r, mid - 1); ++j)
    if (w(j, mid) < w(k, mid)) k = j;
  f[mid] = w(k, mid);
  // 根据决策单调性得出左右两部分的决策区间，递归处理
  if (l < mid) DP(l, mid - 1, k_l, k);
  if (r > mid) DP(mid + 1, r, k, k_r);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def DP(l, r, k_l, k_r):
    mid = int((l + r) / 2)
    k = k_l         # 求状态f[mid]的最优决策点
    for i in range(k_l, min(k_r, mid - 1)):
        if w(i, mid) < w(k, mid):
            k = i
    f[mid] = w(k, mid)         # 根据决策单调性得出左右两部分的决策区间，递归处理
    if l < mid:
        DP(l, mid - 1, k_l, k)
    if r > mid:
        DP(mid + 1, r, k, k_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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

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

掌握这一算法，需要理解如下要点：

• 队列需要记录到目前为止每个可行的决策点 和能够解决的问题区间左右端点 和 构成的 三元组。对于给定区间 内的问题， 应该是到目前为止考虑过的决策点中最小最优的（以下简称最优决策）。每时每刻，队列中存储的决策未必是连续的，但是尚未解决的问题应该是队列中存储的问题区间的不交并。
• 初始化：将首个决策放于队列中，并记录它对于所有问题都是最优的。
• 类似于单调队列，每次考虑下一个决策 的时候，都需要进行出队和入队操作。
• 出队：当所有决策 都考虑结束后，问题 的解就是队列中首个满足 的决策点 。此时可以弹出所有满足 的队首。由于决策单调性，弹出的决策也不会是后续问题的最优决策。
• 入队：要对决策 进行入队时，首先比较它和队尾的决策 。
  • 如果对于问题 ，将入队的决策 比已有的决策 更优，即 时，则弹出队尾的决策 。此操作持续到队尾的决策 比起 对于问题 更优时为止。
  • 如果队列已空，入队 ，即认为决策 是尚未解决的所有问题的最优解。
  • 如果队尾决策 对于问题 同样优于将入队的决策 ，那么当 时，入队 ，表示 是对于问题 的最优解，否则，不需要入队 ，因为它并不比已有的决策更优。
  • 最后的情形是，队尾决策 比起要入队的决策 对于问题 更优，而对于问题 更劣，那么，需要通过 二分 找到最小的 使得 ，将队尾的区间右端点修改为 ，并入队 。

类似于单调队列，每个决策点至多入队一次，出队一次。这里，出队是 的，而入队是 的（可能需要二分），所以总的时间复杂度是 。

例题 1：「POI2011」Lightning Conductor

给定一个长度为 的序列 ，要求对于每一个 ，找到最小的非负整数 满足

参考思路

显然，经过不等式变形，我们可以得到待求整数 。不妨先考虑 的情况（另外一种情况类似），此时我们可以得到状态转移方程：

根据 的凸性，我们很容易得出（后文将详细描述）函数 满足四边形不等式，因此套用上述的算法便可在 的时间内解决此题了。

区间分拆问题

考虑将某个区间拆分成若干个子区间的问题。形式化地说，将给定区间 拆分成 ，其中，，，以及 对任意 都成立。对于给定拆分，成本为 。问题要求最小化这一成本。可以列出如下的 1D1D 状态转移方程。

这里，。注意到，只要 满足四边形不等式， 必然满足四边形不等式，因为第一项并不包括 和 的交叉项，在混合差分时会消去。但是由于成本函数依赖于前面的子问题，这一转移只能够顺序计算，所以通常只适合应用二分队列算法。算法复杂度为 。

参考思路

设 表示将前 个玩具装箱的最小代价，则枚举第 个玩具与哪些玩具放在一个箱子中，可以得到状态转移方程为

记 ，则有 。显然 单调增加，因此根据下文的性质 1 和性质 2 可知 满足区间包含单调性和四边形不等式。再根据 的单调性和凸性以及性质 3 可知， 也满足四边形不等式，此时使用二分队列优化即可。

限制区间个数的情形

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

这里，， 对任意 和 都成立。和上文同样的道理，这里的 必然满足四边形不等式。此时对于第 层的计算，并不再依赖于该层的结果，所以对于每一层，都可以通过分治或者二分队列的方法进行计算，此时算法复杂度为 。

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

证明

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

下证 。假设有如下两个区间 的分划（逆序标号）： 和 。这里，每个区间的左端点都是其右端点处对应问题的最小最优决策；同样地，从右向左考虑可能的分划，应该有右端点也是左端点对应问题的最小最优决策。例如， 和 分别是将 和 分成 段左起第一个区间右端点的最小最优决策。根据决策单调性，如果 ，亦即 ，那么必然有 。由此，如果所证不成立，则有 。进而可以归纳地证明 。这显然与所设矛盾。由此得证。

第一个不等式可以另证如下。同样考虑上面证明中的两个分划。如果所证命题不成立，则有 ，但是由于有 ，我们可以找到最小的 使得 。进而，此时有 ，故 。我们找到了一组区间满足 。考虑将这两个分拆重新组合的结果。考虑分拆 ，共 段，于是由前设的最优性可推知，

同样地，考虑分拆 ，共 段，则有

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

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

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

证明

下证 。为此，考虑长度为 段和 段的最优分划，分别是 和 。取最小的 使得 ，其存在性可由 推知。根据其最小性得知，。所以，。与上文类似，交换两个现有分拆的后半段，可以得到如下两个区间分拆：

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

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

这一结论保证了可以通过 wqs 二分（国外称 Alien's trick）的方法解决此问题。具体来说，考虑带参的成本函数 ，解决不限制区间个数的问题，求得其最优解为 。随着实数 递增，相应的最优区间的数目单调递减，故而可以通过二分的方法找到恰使得最优区间个数等于 的参数 ，则原题最优解为 。这里的实数 可以看作区间个数限制的 Lagrange 乘子。该算法的实现有很多细节，可以参考 专门介绍 wqs 二分的文章。这一算法的时间复杂度为 ，这里 为某一常数。

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

区间合并问题

另一类可以通过四边形不等式优化的动态规划问题是区间合并问题，即要将 个长度为一的区间 两两合并起来，直到得到区间 。每次合并 和 时都需要支付成本 。问题要求找到成本最低的合并方式。对于此类问题，有如下 2D1D 状态转移方程。

这里给定任意初始成本 。暴力算法的总复杂度为 ，而当存在决策单调性时，可以优化至 的算法复杂度。这一算法最早由 Knuth 在解决最优二叉搜索树问题时提出，并由姚储枫进一步研究总结，在国外称为 Knuth's optimization 或 Knuth-Yao speedup。

除了四边形不等式以外，区间合并问题的决策单调性还要求成本函数满足区间包含单调性。

• 区间包含单调性：如果对于任意 均成立

则称函数 对于区间包含关系具有单调性。

这实质是成本函数的一阶条件，即 关于 递减，关于 递增。