四邊形不等式優化

四邊形不等式優化利用的是狀態轉移方程中的決策單調性。

基礎知識

考慮最簡單的情形，我們要解決如下一系列最優化問題。

\[ f(i) = \min_{1 \leq j \leq i} w(j,i) \qquad \left(1 \leq i \leq n\right) \tag{1} \]

這裏假定成本函數 \(w(j,i)\) 可以在 \(O(1)\) 時間內計算。

約定

動態規劃的狀態轉移方程經常可以寫作一系列最優化問題的形式。以（1）式為例，這些問題含有參數 \(i\)，問題的目標函數和可行域都可以依賴於 \(i\)。每一個問題都是在給定參數 \(i\) 時，選取某個可行解 \(j\) 來最小化目標函數的取值。為表述方便，下文將參數為 \(i\) 的最優化問題簡稱為「問題 \(i\)」，該最優化問題的可行解 \(j\) 稱為「決策 \(j\)」，目標函數在最優解處取得的值則稱為「狀態 \(f(i)\)」。同時，記問題 \(i\) 對應的最小最優決策點為 \(\mathop{\mathrm{opt}}(i)\)。

在一般的情形下，這些問題總時間複雜度為 \(O(n^2)\)。這是由於對於問題 \(i\)，我們需要考慮所有可能的決策 \(j\)。而在滿足決策單調性時，可以有效縮小決策空間，優化總複雜度。

• 決策單調性：對於任意 \(i_1 < i_2\)，必然成立 \(\mathop{\mathrm{opt}}(i_1) \leq \mathop{\mathrm{opt}}(i_2)\)。

附註

對於問題 \(i\)，最優決策集合未必是一個區間。決策單調性實際可以定義在最優決策集合上。對於集合 \(A\) 和 \(B\)，可以定義 \(A \leq B\) 當且僅當對於任意 \(a\in A\) 和 \(b\in B\)，成立 \(\min\{a,b\}\in A\) 和 \(\max\{a,b\}\in B\)。這藴含最小（最大）最優決策點的單調性，即此處採取的定義。本文關於最小最優決策點敍述的結論，同樣適用於最大最優決策點。但是，存在情形，某更大問題的最小最優決策嚴格小於另一更小問題的最大最優決策，亦即可能對某些 \(i_1 < i_2\) 成立 \(\mathop{\mathrm{optmax}}(i_1) > \mathop{\mathrm{optmin}}(i_2)\)，所以在書寫代碼時，應保證總是求得最小或最大的最優決策點。

另一方面，擁有相同最小最優決策的問題構成一個區間。這一區間，作為最小最優決策的函數，應嚴格遞增。亦即，給定 \(j_1 = \mathop{\mathrm{opt}}(i_1)\)，\(j_2 = \mathop{\mathrm{opt}}(i_2)\)，如果 \(j_1 < j_2\)，那麼必然有 \(i_1 < i_2\)。換言之，如果決策 \(j_1 < j_2\) 能夠成為最小最優決策的問題區間分別是 \([l_{j_1},r_{j_1}]\) 和 \([l_{j_2},r_{j_2}]\)，那麼必然有 \(r_{j_1} < l_{j_2}\)。

最常見的判斷決策單調性的方法是通過四邊形不等式（quadrangle inequality）。

• 四邊形不等式：如果對於任意 \(a\leq b\leq c\leq d\) 均成立

\[ w(a,c)+w(b,d) \leq w(a,d)+w(b,c), \]

則稱函數 \(w\) 滿足四邊形不等式（簡記為「交叉小於包含」）。若等號永遠成立，則稱函數 \(w\) 滿足 四邊形恆等式。

如果沒有特別説明，以下都會保證 \(a\leq b\leq c\leq d\)。四邊形不等式給出了一個決策單調性的充分不必要條件。

定理 1

若 \(w\) 滿足四邊形不等式，則問題 (1) 滿足決策單調性。

證明

要證明這一點，可採用反證法。假設對某些 \(c < d\)，成立 \(a = \mathop{\mathrm{opt}}(d) < \mathop{\mathrm{opt}}(c) = b\)。此時有 \(a < b \leq c < d\)。根據最優化條件，\(w(a,d) \leq w(b,d)\) 且 \(w(b,c) < w(a,c)\)，於是，\(w(a,d) - w(b,d) \leq 0 < w(a,c) - w(b,c)\)，這與四邊形不等式矛盾。

四邊形不等式可以理解在合理的定義域內，\(w\) 的二階混合差分 \(\Delta_i\Delta_jw(j,i)\) 非正。

利用決策單調性，有兩種常見算法可以將算法複雜度優化到 \(O(n\log n)\)。

分治

要求解所有狀態，只需要求解所有最優決策點。為了對所有 \(1 \leq i \leq n\) 求解 \(\mathop{\mathrm{opt}}(i)\)，首先計算 \(\mathop{\mathrm{opt}}(n/2)\)，而後分別計算 \(1 \leq i < n/2\) 和 \(n/2 < i \leq n\) 上的 \(\mathop{\mathrm{opt}}(i)\)，注意此時已知前半段的 \(\mathop{\mathrm{opt}}(i)\) 必然位於 \(1\) 和 \(\mathop{\mathrm{opt}}(n/2)\) 之間（含端點），而後半段的 \(\mathop{\mathrm{opt}}(i)\) 必然位於 \(\mathop{\mathrm{opt}}(n/2)\) 和 \(\mathop{\mathrm{opt}}(n)\) 之間（含端點）。對於兩個子區間，也類似處理，直至計算出每個問題的最優決策。在分治的過程中記錄搜索的上下邊界，就可以保證算法複雜度控制在 \(O(n\log n)\)。遞歸樹層數為 \(O(\log n)\)，而每層中，單個決策點至多計算兩次，所以總的計算次數是 \(O(n\log n)\)。

核心代碼

C++Python

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);
}

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)

二分隊列

注意到對於每個決策點 \(j\)，能使其成為最小最優決策點的問題 \(i\) 必然構成一個區間。可以通過單調隊列記錄到目前為止每個決策點可以解決的問題的區間，這樣，問題的最優解自然可以通過隊列中記錄的決策點計算得到。算法大致如下。

核心代碼

C++

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;
  }
}

掌握這一算法，需要理解如下要點：

• 隊列需要記錄到目前為止每個可行的決策點 \(j\) 和能夠解決的問題區間左右端點 \(l_j\) 和 \(r_j\) 構成的 三元組。對於給定區間 \([l_j,r_j]\) 內的問題，\(j\) 應該是到目前為止考慮過的決策點中最小最優的（以下簡稱最優決策）。每時每刻，隊列中存儲的決策未必是連續的，但是尚未解決的問題應該是隊列中存儲的問題區間的不交併。
• 初始化：將首個決策放於隊列中，並記錄它對於所有問題都是最優的。
• 類似於單調隊列，每次考慮下一個決策 \(j\) 的時候，都需要進行出隊和入隊操作。
• 出隊：當所有決策 \(j \leq i\) 都考慮結束後，問題 \(i\) 的解就是隊列中首個滿足 \(l_j \leq i \leq r_j\) 的決策點 \(j\)。此時可以彈出所有滿足 \(r_j < i\) 的隊首。由於決策單調性，彈出的決策也不會是後續問題的最優決策。
• 入隊：要對決策 \(j\) 進行入隊時，首先比較它和隊尾的決策 \(j'\)。
  • 如果對於問題 \(l_{j'}\)，將入隊的決策 \(j\) 比已有的決策 \(j'\) 更優，即 \(w(j,l_{j'}) < w(j',l_{j'})\) 時，則彈出隊尾的決策 \(j'\)。此操作持續到隊尾的決策 \(j'\) 比起 \(j\) 對於問題 \(l_{j'}\) 更優時為止。
  • 如果隊列已空，入隊 \((j,j+1,n)\)，即認為決策 \(j\) 是尚未解決的所有問題的最優解。
  • 如果隊尾決策 \(j'\) 對於問題 \(r_{j'}\) 同樣優於將入隊的決策 \(j\)，那麼當 \(r_{j'} < n\) 時，入隊 \((j,r_{j'}+1,n)\)，表示 \(j\) 是對於問題 \([r_{j'}+1,n]\) 的最優解，否則，不需要入隊 \(j\)，因為它並不比已有的決策更優。
  • 最後的情形是，隊尾決策 \(j'\) 比起要入隊的決策 \(j\) 對於問題 \(l_{j'}\) 更優，而對於問題 \(r_{j'}\) 更劣，那麼，需要通過 二分 找到最小的 \(i\in[l_{j'},r_{j'}]\) 使得 \(w(j,i) < w(j',i)\)，將隊尾的區間右端點修改為 \(i-1\)，併入隊 \((j,i,n)\)。

類似於單調隊列，每個決策點至多入隊一次，出隊一次。這裏，出隊是 \(O(1)\) 的，而入隊是 \(O(\log n)\) 的（可能需要二分），所以總的時間複雜度是 \(O(n\log n)\)。

例題 1：「POI2011」Lightning Conductor

給定一個長度為 \(n\) 的序列 \(a_1,a_2,\cdots,a_n\)，要求對於每一個 \(1 \leq i \leq n\)，找到最小的非負整數 \(f_i\) 滿足

\[ \forall j\in\left[1,n\right]:a_j \leq a_i + f_i - \sqrt{|i-j|}. \]

參考思路

顯然，經過不等式變形，我們可以得到待求整數 \(f_i = \max_{j}\{a_j+\sqrt{|i-j|}-a_i\}\)。不妨先考慮 \(j \leq i\) 的情況（另外一種情況類似），此時我們可以得到狀態轉移方程：

\[ f_i = \min_{j\le i}\{-a_j-\sqrt{i-j}+a_i\}. \]

根據 \(-\sqrt{x}\) 的凸性，我們很容易得出（後文將詳細描述）函數 \(w(l, r) = -a_l - \sqrt{r-l} + a_r\) 滿足四邊形不等式，因此套用上述的算法便可在 \(O(n\log n)\) 的時間內解決此題了。

區間分拆問題

考慮將某個區間拆分成若干個子區間的問題。形式化地説，將給定區間 \([1,n]\) 拆分成 \([a_1,b_1],\cdots,[a_k,b_k]\)，其中，\(b_1=1\)，\(a_k=n\)，以及 \(b_{i}+1=a_{i+1}\) 對任意 \(i < k\) 都成立。對於給定拆分，成本為 \(\sum_{i=1}^kw(a_i,b_i)\)。問題要求最小化這一成本。可以列出如下的 1D1D 狀態轉移方程。

\[ f(i) = \min_{1\leq j\leq i} f(j-1)+w(j,i) \qquad (1\leq i\leq n) \]

這裏，\(f(0)=0\)。注意到，只要 \(w(j,i)\) 滿足四邊形不等式，\(f(j-1)+w(j,i)\) 必然滿足四邊形不等式，因為第一項並不包括 \(j\) 和 \(i\) 的交叉項，在混合差分時會消去。但是由於成本函數依賴於前面的子問題，這一轉移只能夠順序計算，所以通常只適合應用二分隊列算法。算法複雜度為 \(O(n\log n)\)。

例題 2：「HNOI2008」玩具裝箱 toy

有 \(n\) 個玩具需要裝箱，要求每個箱子中的玩具編號必須是連續的。每個玩具有一個長度 \(C_i\)，如果一個箱子中有多個玩具，那麼每兩個玩具之間要加入一個單位長度的分隔物。形式化地説，如果將編號在 \([j,i]\) 間的玩具裝在一個箱子裏，那麼這個箱子的長度為 \(i-j+\sum_{k=j}^i C_k\)。現在需要制定一個裝箱方案，使得所有容器的長度與 \(K\) 差值的平方之和最小。

參考思路

設 \(f_i\) 表示將前 \(i\) 個玩具裝箱的最小代價，則枚舉第 \(i\) 個玩具與哪些玩具放在一個箱子中，可以得到狀態轉移方程為

\[ f_{i} = \min_{j=1}^{i}f_{j-1} + \left(i-j+\sum_{k=j}^i C_k\right)^2. \]

記 \(s(i) = i+\sum_{k=1}^i C_k\)，則有 \(w(j, i) = \left(s(i) - s(j - 1) - 1 - K\right)^2\)。顯然 \(s(i)\) 單調增加，因此根據下文的性質 1 和性質 2 可知 \(s(i) - s(j - 1) - 1 - K\) 滿足區間包含單調性和四邊形不等式。再根據 \(x^2\) 的單調性和凸性以及性質 3 可知，\(w(j, i)\) 也滿足四邊形不等式，此時使用二分隊列優化即可。

限制區間個數的情形

上述問題可以加強為限制區間個數的情形，即問題指定將區間拆分成 \(m\) 個子區間。此時需要將拆分後的區間個數作為轉移狀態的一維。相應地，有 2D1D 狀態轉移方程如下。

\[ f(k,i) = \min_{1\leq j\leq i} f(k-1,j-1)+w(j,i) \qquad (1\leq k\leq m,\ 1\leq i\leq n) \tag{2} \]

這裏，\(f(0,0)=0\)，\(f(0,i)=f(k,0)=\infty\) 對任意 \(1\leq k\leq m\) 和 \(1\leq i\leq n\) 都成立。和上文同樣的道理，這裏的 \(f(k-1,j-1)+w(j,i)\) 必然滿足四邊形不等式。此時對於第 \(i\) 層的計算，並不再依賴於該層的結果，所以對於每一層，都可以通過分治或者二分隊列的方法進行計算，此時算法複雜度為 \(O(mn\log n)\)。

對於這一問題，利用決策單調性，實際上還存在其他的優化算法。第二種優化思路依賴於如下結果。這種優化算法和下文詳細描述的 Knuth 優化算法十分相似。

定理 2

若 \(w\) 滿足四邊形不等式，則對於問題 (2) 成立 \(\mathop{\mathrm{opt}}(k-1,i) \leq \mathop{\mathrm{opt}}(k,i) \leq \mathop{\mathrm{opt}}(k,i+1)\)。

證明

第二個不等式只是第 \(k\) 層的決策單調性。關鍵在於第一個不等式。

下證 \(\mathop{\mathrm{opt}}(k,i) \leq \mathop{\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-1} > b_{j-1}\)，亦即 \(d_j > c_j\)，那麼必然有 \(a_j > c_j\)。由此，如果所證不成立，則有 \(a_1 > b_1\)。進而可以歸納地證明 \(a_{k} > b_{k}\)。這顯然與所設矛盾。由此得證。

第一個不等式可以另證如下。同樣考慮上面證明中的兩個分劃。如果所證命題不成立，則有 \(a_1 > b_1\)，但是由於有 \(a_{k} < b_{k}\)，我們可以找到最小的 \(j>1\) 使得 \(a_j \leq b_j\)。進而，此時有 \(a_{j-1} > b_{j-1}\)，故 \(d_j>c_j\)。我們找到了一組區間滿足 \(a_j \leq b_j \leq c_j < d_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)\) 段，於是由前設的最優性可推知，

\[ \begin{aligned} &w(b_{k+1},c_{k+1})+\cdots+w(b_{j+1},c_{j+1})+w(b_j,c_j)+w(b_{j-1},c_{j-1})+\cdots+w(b_1,c_1) \\ &\qquad \leq w(b_{k+1},c_{k+1})+\cdots+w(b_{j+1},c_{j+1})+w(b_j,d_j)+w(a_{j-1},d_{j-1})+\cdots+w(a_1,d_1). \end{aligned} \]

同樣地，考慮分拆 \([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\) 段，則有

\[ \begin{aligned} &w(a_{k},d_{k})+\cdots+w(a_{j+1},d_{j+1})+w(a_j,d_j)+w(a_{j-1},d_{j-1})+\cdots+w(a_1,d_1) \\ &\qquad < w(a_{k},d_{k})+\cdots+w(a_{j+1},d_{j+1})+w(a_j,c_j)+w(b_{j-1},c_{j-1})+\cdots+w(b_1,c_1). \end{aligned} \]

此時，不等號是嚴格的，因為 \(a_1 > b_1\)，但是按假設，\(a_1\) 是所有 \(k\) 段分拆最末一段的左端點中最小最優的。兩個不等式條件相加，得到 \(w(b_j,c_j) + w(a_j,d_j) < w(b_j,d_j) + w(a_j,c_j)\)，這有悖於四邊形不等式。故而原結論得證。

利用這一結果，我們可以限制決策 \(j\) 的搜索範圍。算法實現時，對 \(k\) 正向遍歷，對 \(i\) 逆向遍歷，在之前已確定的上下界範圍內暴力搜索 \(j\) 就可以保證 \(O(n(n+m))\) 的算法複雜度。

注意

這裏算法複雜度不是 \(O(nm)\) 的。正確的複雜度計算需要考慮 \(n\times m\) 維狀態矩陣。因為對於問題 \((i,k)\) 只需要考慮 \(\mathop{\mathrm{opt}}(k-1,i) \leq j \leq \mathop{\mathrm{opt}}(k,i+1)\) 中的決策，所以每條次對角線上（即 \(i-k\) 為一定值）的問題所需遍歷的決策總數為 \(O(n)\) 的。這樣的對角線共計 \((n+m)\) 條，故而總的時間複雜度為 \(O(n(n+m))\)。

最後一種優化方法來源於如下的觀察。

定理 3

若 \(w\) 滿足四邊形不等式，則問題 (2) 的最優解 \(g(k):=f(n,k)\) 是關於 \(k\) 的凸函數。

證明

下證 \(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 \leq j \leq k-1\) 使得 \(c_{j+1} \leq d_j\)，其存在性可由 \(c_{k} < n = d_{k-1}\) 推知。根據其最小性得知，\(b_{j+1} > a_j\)。所以，\(a_j < b_{j+1} \leq c_{j+1} \leq d_j\)。與上文類似，交換兩個現有分拆的後半段，可以得到如下兩個區間分拆：

\[ \begin{aligned} & [a_1,d_1],\cdots,[a_{j-1},d_{j-1}],[a_j,c_{j+1}],[b_{j+2},c_{j+2}],\cdots,[b_{k+1},c_{k+1}], \\ & [b_1,c_1],\cdots,[b_j,c_j],[b_{j+1},d_j],[a_{j+1},d_{j+1}],\cdots,[a_{k-1},d_{k-1}]. \end{aligned} \]

兩個所得區間都是 \(k\) 段的，所以由最優性條件可知

\[ \begin{aligned} 2g(k) &\le w(a_1,d_1) + \cdots + w(a_{j-1},d_{j-1}) + w(a_j,c_{j+1}) + w(b_{j+2},c_{j+2}) + \cdots + w(b_{k+1},c_{k+1}) \\ &\quad + w(b_1,c_1) + \cdots + w(b_j,c_j) + w(b_{j+1},d_j) + w(a_{j+1},d_{j+1}) + \cdots + w(a_{k-1},d_{k-1}) \\ &\le w(a_1,d_1) + \cdots + w(a_{j-1},d_{j-1}) + w(a_j,d_j) + w(a_{j+1},d_{j+1}) + \cdots + w(a_{k-1},d_{k-1}) \\ &\quad + w(b_1,c_1) + \cdots + w(b_j,c_j) + w(b_{j+1},c_{j+1}) + w(b_{j+2},c_{j+2}) + \cdots + w(b_{k+1},c_{k+1}) \\ &= g(k-1) + g(k+1). \end{aligned} \]

這裏第二個不等式正是四邊形不等式。所求凸性由此得證。

這一結論保證了可以通過 wqs 二分（國外稱 Alien's 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\) 為某一常數。

對於限制區間個數的區間分拆問題的三種算法，在不同的數據範圍時表現各有優劣，需要結合具體的題目選擇合適的算法。

區間合併問題

另一類可以通過四邊形不等式優化的動態規劃問題是區間合併問題，即要將 \(n\) 個長度為一的區間 \([i,i]\) 兩兩合併起來，直到得到區間 \([1,n]\)。每次合併 \([j,k]\) 和 \([k+1,i]\) 時都需要支付成本 \(w(j,i)\)。問題要求找到成本最低的合併方式。對於此類問題，有如下 2D1D 狀態轉移方程。

\[ f(j,i) = \min_{j \leq k < i} f(j,k) + f(k+1,i) + w(j,i) \qquad (1\le j< i\le n) \tag{3} \]

這裏給定任意初始成本 \(f(i,i)=w(i,i)\)。暴力算法的總複雜度為 \(O(n^3)\)，而當存在決策單調性時，可以優化至 \(O(n^2)\) 的算法複雜度。這一算法最早由 Knuth 在解決最優二叉搜索樹問題時提出，並由姚儲楓進一步研究總結，在國外稱為 Knuth's optimization 或 Knuth-Yao speedup。

除了四邊形不等式以外，區間合併問題的決策單調性還要求成本函數滿足區間包含單調性。

• 區間包含單調性：如果對於任意 \(a \leq b \leq c \leq d\) 均成立

\[ w(b,c) \leq w(a,d), \]

則稱函數 \(w\) 對於區間包含關係具有單調性。

這實質是成本函數的一階條件，即 \(w(j,i)\) 關於 \(j\) 遞減，關於 \(i\) 遞增。

引理 1

若 \(w\) 滿足區間包含單調性和四邊形不等式，則狀態 \(f(j,i)\) 滿足四邊形不等式。

證明

不妨設 \(a \leq b \leq c \leq d\)。下證 \(f(a,d) + f(b,c) \geq f(a,c) + f(b,d)\)。考慮依 \(d-a\) 歸納。當 \(a=b\) 或 \(c=d\) 時，所求即一等式。對於一般的情形，根據 \(d'=\mathop{\mathrm{opt}}(a,d)\) 的位置分類討論。

第一種情況，\(c \leq d'\) 或 \(d' < b\)，即 \([b,c]\) 包含於 \([a,d']\) 或 \([d'+1,d]\) 之中。

不妨假設 \(c \leq d'\)，另一種情形同理。此時有

\[ \begin{aligned} f(a,d) + f(b,c) & = f(a,d') + f(d'+1,d) + w(a,d) + f(b,c) \\ & \geq f(a,c) + f(b,d') + f(d'+1,d) + w(a,d) \\ & \geq f(a,c) + f(b,d') + f(d'+1,d) + w(b,d) \\ & \geq f(a,c) + f(b,d). \end{aligned} \]

這裏，第一個不等式來自於歸納假設 \(f(a,c) + f(b,d') \leq f(a,d') + f(b,c)\)，第二個不等式來自於區間包含單調性 \(w(b,d) \leq w(a,d)\)，第三個不等式來自於最優性條件 \(f(b,d) \leq f(b,d') + f(d'+1,d) + w(b,d)\)。

第二種情況，\(b \leq d' < c\)，即 \(d'\) 位於 \([b,c]\) 之中。此時，考慮 \(c'=\mathop{\mathrm{opt}}(b,c)\) 的位置。

不妨假設 \(c' \leq d'\)，即 \([b,c']\) 包含於 \([a,d']\) 之中，另一種情形同理。此時有

\[ \begin{aligned} f(a,d) + f(b,c) & = f(a,d') + f(d'+1,d) + w(a,d) + f(b,c') + f(c'+1,c) + w(b,c) \\ & \geq f(a,c') + f(c'+1,c) + w(b,c) + f(b,d') + f(d'+1,d) + w(a,d) \\ & \geq f(a,c') + f(c'+1,c) + w(a,c) + f(b,d') + f(d'+1,d) + w(b,d) \\ & \geq f(a,c) + f(b,d). \end{aligned} \]

這裏，第一個不等式來自於歸納假設 \(f(a,c') + f(b,d') \leq f(a,d') + f(b,c')\)，第二個不等式來自於四邊形不等式 \(w(a,c) + w(b,d) \leq w(a,d) + w(b,c)\)，第三個不等式來自於 \(f(a,c)\) 和 \(f(b,d)\) 的最優性條件。

定理 4

若 \(w\) 滿足區間包含單調性和四邊形不等式，則問題 (3) 中最小最優決策 \(\mathop{\mathrm{opt}}(j,i)\) 滿足

\[ \mathop{\mathrm{opt}}(j,i-1) \leq \mathop{\mathrm{opt}}(j,i) \leq \mathop{\mathrm{opt}}(j+1,i). \qquad (j + 1 < i) \]

證明

引理 1 已經證得 \(f(j,i)\) 滿足四邊形不等式，所以目標函數 \(f(j,k) + f(k+1,i) + w(j,i)\) 對於給定 \(j\) 作為 \((k,i)\) 的函數滿足四邊形不等式，所以由定理 1 有，\(\mathop{\mathrm{opt}}(j,i-1) \leq \mathop{\mathrm{opt}}(j,i)\)。注意，不同時含有 \((k,i)\) 的項並不影響四邊形不等式成立。類似地，它對於給定 \(i\) 作為 \((k,j)\) 的函數也滿足四邊形不等式，所以 \(\mathop{\mathrm{opt}}(j,i) \leq \mathop{\mathrm{opt}}(j+1,i)\)。即得所證。

利用這一結論，同樣可以限制決策點 \(k\) 的搜索範圍。在這裏，正序遍歷區間長度 \(i-j+1\)，再遍歷具有同樣長度的所有區間 \([j,i]\)，暴力搜索 \(\mathop{\mathrm{opt}}(j,i-1)\) 和 \(\mathop{\mathrm{opt}}(j+1,i)\) 之間的所有 \(k\) 求得最優解 \(f(j,i)\) 並記錄最小最優決策 \(\mathop{\mathrm{opt}}(j,i)\)。對於同樣長度的所有區間，此算法中決策空間總長度是 \(O(n)\) 的，而可能的區間長度的數目同樣是 \(O(n)\) 的，故而總的算法複雜度為 \(O(n^2)\) 的。

核心代碼

C++Python

for (int len = 2; len <= n; ++len)  // 枚舉區間長度
  for (int j = 1, i = len; i <= n; ++j, ++i) {
    // 枚舉長度為len的所有區間
    f[j][i] = INF;
    for (int k = opt[j][i - 1]; k <= opt[j + 1][i]; ++k)
      if (f[j][i] > f[j][k] + f[k + 1][i] + w(j, i)) {
        f[j][i] = f[j][k] + f[k + 1][i] + w(j, i);  // 更新狀態值
        opt[j][i] = k;  // 更新（最小）最優決策點
      }
  }

for len in range(2, n + 1): # 枚舉區間長度
    for i in range(len, n + 1):
        # 枚舉長度為len的所有區間
        j = i - len + 1
        f[j][i] = INF
        for k in range(opt[j][i - 1], opt[j + 1][i] + 1):
            if f[j][i] > f[j][k] + f[k + 1][i] + w(j, i):
                f[j][i] = f[j][k] + f[k + 1][i] + w(j, i) # 更新狀態值
                opt[j][i] = k # 更新（最小）最優決策點

滿足四邊形不等式的函數類

為了更方便地證明一個函數滿足四邊形不等式，我們有以下幾條性質：

性質 1：若函數 \(w_1(j,i)\) 和 \(w_2(j,i)\) 均滿足四邊形不等式（或區間包含單調性），則對於任意 \(c_1,c_2\geq 0\)，函數 \(c_1w_1+c_2w_2\) 也滿足四邊形不等式（或區間包含單調性）。

性質 2：若存在函數 \(f(x)\) 和 \(g(x)\) 使得 \(w(j,i) = f(j)-g(i)\)，則函數 \(w\) 滿足四邊形恆等式。當函數 \(f\) 和 \(g\) 單調增加時，函數 \(w\) 還滿足區間包含單調性。

性質 3：設 \(h(x)\) 是一個單調增加的凸函數，若函數 \(w(j,i)\) 滿足四邊形不等式並且對區間包含關係具有單調性，則複合函數 \(h(w(j,i))\) 也滿足四邊形不等式和區間包含單調性。

性質 4：設 \(h(x)\) 是一個凸函數，若函數 \(w(j,i)\) 滿足四邊形恆等式並且對區間包含關係具有單調性，則複合函數 \(h(w(j,i))\) 也滿足四邊形不等式。

首先需要澄清一點，凸函數（Convex Function）的定義在國內教材中有分歧，此處的凸函數指的是下凸函數，即（可微時）一階導數單調增加的函數。

證明

前兩條性質根據定義很容易證明，下面證明第三條性質，性質四的證明過程類似。由於 \(h(x)\) 單調，\(h(w(j,i))\) 自然保持對區間包含的單調性。關鍵在於四邊形不等式的證明。

為此，下面考慮 \(a \leq j \leq b \leq c \leq i \leq d\) 上的二階混合差分。

\[ \begin{aligned} \Delta_i\Delta_j h\left(w(j,i)\right) &= h\left(w(b,d)\right) - h\left(w(a,c) + \Delta_jw(j,c) + \Delta_iw(a,i)\right) \\ &\quad + h\left(w(a,c) + \Delta_jw(j,c) + \Delta_iw(a,i)\right) - h\left(w(a,c) + \Delta_jw(j,c)\right) \\ &\quad - h\left(w(a,c) + \Delta_iw(a,i)\right) + h\left(w(a,c)\right). \end{aligned} \]

這裏，根據區間單調性，\(\Delta_iw(a,i) := w(a,d) - w(a,c) \geq 0\) 和 \(\Delta_jw(j,c) := w(b,c) - w(a,c) \leq 0\)。由於 \(h(x)\) 具有凸性，對於 \(t_1,t_2\geq 0\) 成立 \(h(x + t_1 - t_2) - h(x + t_1) \leq h(x - t_2) - h(x)\)，所以後兩行必然非正。同時，由於四邊形不等式，\(w(b,d) \leq w(a,c) + \Delta_jw(j,c) + \Delta_iw(a,i) = w(b,c) + w(a,d) - w(a,c)\)，故而，第一行的差在 \(h(x)\) 單調增加的情況下必然也非正。所以，總的二階混合差分非正。此即四邊形不等式。

這一證明實際是如下導數證明的離散版本。

\[ \frac{\partial^2}{\partial x\partial y}h(w(x,y)) = h''(w(x,y))\frac{\partial }{\partial x}w(x,y)\frac{\partial}{\partial y}w(x,y) + h'(w(x,y))\frac{\partial^2}{\partial x\partial y}w(x,y) \leq 0. \]

這在 \(h' \geq 0\)，\(h'' \geq 0\)，\(w_x \leq 0\)，\(w_y \geq 0\) 以及 \(w_{xy} \leq 0\) 的條件下顯然成立。其中，區間包含單調性給出了 \(w\) 的一階條件，而四邊形不等式給出了其二階條件。

習題

• 「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

參考資料

• noiau 的 CSDN 博客
• Quora Answer by Michael Levin
• Video Tutorial by "Sothe" the Algorithm Wolf
• Divide and Conquer DP
• Knuth's Optimization
• Quadrangle Inequality Properties
• 王欽石《淺析一類二分方法》

---

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