

四边形不等式优化

区间类（2D1D）动态规划中的应用¶

在区间类动态规划（如石子合并问题）中，我们经常遇到以下形式的 2D1D 状态转移方程：

直接简单实现状态转移，总时间复杂度将会达到，但当函数满足一些特殊的性质时，我们可以利用决策的单调性进行优化。

区间包含单调性：如果对于任意，均有成立，则称函数对于区间包含关系具有单调性。
四边形不等式：如果对于任意，均有成立，则称函数满足四边形不等式（简记为“交叉小于包含”）。若等号永远成立，则称函数满足 四边形恒等式。

引理 1：若满足区间包含单调性和四边形不等式，则状态满足四边形不等式。

定义表示当决策为时的状态值，任取，记分别表示状态和的最小最优决策点。

注意到，仅当时才有意义。因此我们有必要单独考虑的情形。

首先注意到若或时，显然成立。

考虑对区间长度使用数学归纳法（时，显然成立）。

（证明过程需要满足区间包含单调性）
1. 若则，由归纳法，两式相加再消去相同部分得到（下面最后一个不等式用到了）：
2. 若则由归纳法，两式相加再消去相同部分得到（下面最后一个不等式用到了）：
（仅需要满足四边形不等式）
1. 若，则，因此
  
  再由和归纳假设知
  
  将前两个不等式累加，并将第三个不等式代入，可得
2. 若，则，因此
  
  再由和归纳假设知
  
  将前两个不等式累加，并将第三个不等式代入，可得

综上所述，两种情形均有，即四边形不等式成立。

定理 1：若状态满足四边形不等式，记表示最优决策点，则有

记，分情况讨论：

若，则，因此根据四边形不等式有

再根据是状态的最优决策点可知

将以上两个不等式相加，得

即，但这与是最小的最优决策点矛盾，因此。
若，则，根据四边形不等式可得

再根据是状态的最优决策点可知

将以上两个不等式相加，得

即，但这与是最小的最优决策点矛盾，因此。

因此，如果在计算状态的同时将其最优决策点记录下来，那么我们对决策点的总枚举量将降为

核心代码

// C++ Version
for (int len = 2; len <= n; ++len)  // 枚举区间长度
  for (int l = 1, r = len; r <= n; ++l, ++r) {
    // 枚举长度为len的所有区间
    f[l][r] = INF;
    for (int k = m[l][r - 1]; k <= m[l + 1][r]; ++k)
      if (f[l][r] > f[l][k] + f[k + 1][r] + w(l, r)) {
        f[l][r] = f[l][k] + f[k + 1][r] + w(l, r);  // 更新状态值
        m[l][r] = k;  // 更新（最小）最优决策点
      }
  }

# Python Version
for len in range(2, n + 1): # 枚举区间长度
    r = len
    l = 1
    while(r <= n):
        # 枚举长度为len的所有区间
        r += 1
        l += 1
        f[l][r] = INF
        k = m[l][r - 1]
        while k <= m[l + 1][r]:
            if f[l][r] > f[l][k] + f[k + 1][r] + w(l, r):
                f[l][r] = f[l][k] + f[k + 1][r] + w(l, r) # 更新状态值
                m[l][r] = k # 更新（最小）最优决策点
            k += 1

另一种常见的形式¶

某些 dp 问题有着如下的形式：

总共有个状态，每个状态要有次转换，上述 dp 问题的时间复杂度就是。

实际上此形式也有同样的结论，可以在复杂度解决，读者可以模仿 2D1D 类似的给出证明。

令为使上述表达式最小化的的值。如果对于所有的都有，那么我们就可以用分治法来优化 dp 问题。

我们可以更有效地解出所有状态。假设我们对于固定的和计算。那么我们就可以确定对于任何都有，这意味着在计算时，我们不必考虑那么多其他的点。

为了最小化运行时间，我们便需要应用分治法背后的思想。首先计算然后计算。通过递归地得到的上下界，就可以达到的时间复杂度。每一个的值只可能出现在个不同的节点中。

参考代码

int n;
long long C(int i, int j);
vector<long long> dp_before(n), dp_cur(n);
// compute dp_cur[l], ... dp_cur[r] (inclusive)
void compute(int l, int r, int optl, int optr) {
  if (l > r) return;
  int mid = (l + r) >> 1;
  pair<long long, int> best = {INF, -1};
  for (int k = optl; k <= min(mid, optr); k++) {
    best = min(best, {dp_before[k] + C(k, mid), k});
  }
  dp_cur[mid] = best.first;
  int opt = best.second;
  compute(l, mid - 1, optl, opt);
  compute(mid + 1, r, opt, optr);
}

1D1D 动态规划中的应用¶

除了经典的石子合并问题外，四边形不等式的性质在一类 1D1D 动态规划中也能得出决策单调性，从而优化状态转移的复杂度。考虑以下状态转移方程：

定理 2：若函数满足四边形不等式，记表示从转移过来的状态 , 表示最小最优决策点，则有

记，若，则，根据四边形不等式有

又由于是最优决策点，因此，即

将以上两个不等式相加，可得

即，但这与是最小最优决策点矛盾，因此必有。

但与 2D1D 动态规划中的情形不同，在这里我们根据决策单调性只能得出每次枚举时的下界，而无法确定其上界。因此，简单实现该状态转移方程仍然无法优化最坏时间复杂度。

先考虑一种简单的情况，转移函数的值在动态规划前就已完全确定。即如下所示状态转移方程：

在这种情况下，我们定义过程表示求解的状态值，并且已知这些状态的最优决策点必定位于中，然后使用分治算法如下：

代码实现

// C++ Version
void DP(int l, int r, int k_l, int k_r) {
  int mid = (l + r) / 2, k = k_l;
  // 求状态f[mid]的最优决策点
  for (int i = k_l; i <= min(k_r, mid - 1); ++i)
    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);
}

# Python Version
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)

使用递归树的方法，容易分析出该分治算法的复杂度为，因为递归树每一层的决策区间总长度不超过，而递归层数显然为级别。

「POI2011」Lightning Conductor ¶

题目大意

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

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

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

现在处理一般情况，即转移函数的值是在动态规划的过程中按照一定的拓扑序逐步确定的。此时我们需要改变思维方式，由“确定一个状态的最优决策”转化为“确定一个决策是哪些状态的最优决策“。具体可见上文的「单调栈优化 DP」。

满足四边形不等式的函数类¶

为了更方便地证明一个函数满足四边形不等式，我们有以下几条性质：

性质 1：若函数均满足四边形不等式（或区间包含单调性），则对于任意，函数也满足四边形不等式（或区间包含单调性）。

性质 2：若存在函数使得，则函数满足四边形恒等式。当函数单调增加时，函数还满足区间包含单调性。

性质 3：设是一个单调增加的凸函数，若函数满足四边形不等式并且对区间包含关系具有单调性，则复合函数也满足四边形不等式和区间包含单调性。

性质 4：设是一个凸函数，若函数满足四边形恒等式并且对区间包含关系具有单调性，则复合函数也满足四边形不等式。

首先需要澄清一点，凸函数（Convex Function）的定义在国内教材中有分歧，此处的凸函数指的是（可微的）下凸函数，即一阶导数单调增加的函数。

前两条性质根据定义很容易证明，下面证明第三条性质，性质四的证明过程类似。

任取，根据函数对区间包含关系的单调性有成立。又因为单调增加，故，即复合函数满足区间包含单调性。

任取，根据函数满足四边形不等式，有

移项，并根据对区间包含满足单调性，可得

记，则，故根据函数的单调性可知（如果是证明性质四则第一个不等式变为等式，无需用到单调性）

设，则。由于是一个凸函数，故导函数单调增加，因此函数也单调增加，此时有

即，说明也满足四边形不等式。

回顾例题 1 中的，由性质 2 可知满足四边形不等式，而满足四边形恒等式和区间包含单调性。再根据的凸性以及性质 4 可知也满足四边形不等式，最终利用性质 1，即可得出满足四边形不等式性质了。

「HNOI2008」玩具装箱 toy ¶

题目大意

有个玩具需要装箱，要求每个箱子中的玩具编号必须是连续的。每个玩具有一个长度，如果一个箱子中有多个玩具，那么每两个玩具之间要加入一个单位长度的分隔物。形式化地说，如果将编号在间的玩具装在一个箱子里，那么这个箱子的长度为。现在需要制定一个装箱方案，使得所有容器的长度与差值的平方之和最小。

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

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

习题¶

「IOI2000」邮局
Codeforces - Ciel and Gondolas(Be careful with I/O!)
SPOJ - LARMY
Codechef - CHEFAOR
Hackerrank - Guardians of the Lunatics
ACM ICPC World Finals 2017 - Money

参考资料¶

本页面主要译自英文版博文 Divide and Conquer DP。版权协议为 CC-BY-SA 4.0。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Marcythm, zyf0726, hsfzLZH1, MingqiHuang, Ir1d, greyqz, billchenchina, Chrogeek, StudyingFather
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用