四邊形優化

概述

四邊形優化是 DP 優化中一個相當複雜的一個章節，主要處理 1D/1D 跟 2D/1D 的某些型態的 DP。

因為我個人認為實用>證明，所以以下會省略掉大部分不太重要的證明。畢竟證明就算知道了那也沒怎樣，不如直接把定理記起來。(我還是有證一些比較重要的證明)

其中關於 1D/1D 的 DP 會以決策單調性的角度來說明四邊形優化並且在過程中講述分治優化以及四邊形不等式的關係。

1D/1D DP 與決策單調性

讓我們先來回顧一下前兩章。前兩章的內容是討論兩種不同 1D/1D DP 的一些特別情形的優化。這裡我們先放上那兩個優化的轉移式：

單調隊列優化： $dp(i)=h(i)+\max\limits_{l(i)\leq j\leq r(i)}\{A(j)\}$

斜率優化： $dp(i)=h(i)+\max\limits_{j\leq r(i)}\{A(j)X(i)+B(j)\}$ (這章節考慮 $A,B$ 為遞增函數，也就是斜率、查詢都遞增)

這兩種優化都是基於決策單調性來將複雜度優化到 $O(N)$ 。那麼你可能會好奇，還有什麼情況是可以使用決策單調性的呢？接下來我們給出一個更推廣的原理：四邊形不等式與決策單調性

決策單調性適用原理：四邊形不等式與決策單調性

這裡先再次放上 1D/1D DP 的標準轉移式

$dp(i)=\max(min)\{dp(j)+w(i,j)\}$

四邊形不等式：若 $w(i,j)$ 滿足四邊形不等式，那麼對於任意 $a\leq b\leq c\leq d$ ，皆有 $w(a,c)+w(b,d)\leq (\geq)\ w(a,d)+w(b,c)$

要注意的是，這裡的四邊形不等式並非代數上的不等式。他只是 $w$ 這個函數所具備的特別性質。

那麼我們會有以下定理：

定理1：若 $w(i,j)$ 滿足四邊形不等式，那麼這個 1D/1D DP 具有決策單調性

不同的 min/max 跟大小於符號適用的 DP 跟單調性是有些許差別的，下面分出四種情形，這四種情形都具備決策單調性：

當四邊形不等式不等號為 $\leq$ 時，若轉移方程取 min，那麼最優決策點的方向跟 $i$ 移動的方向相同
當四邊形不等式不等號為 $\leq$ 時，若轉移方程取 max，那麼最優決策點的方向跟 $i$ 移動的方向相反
當四邊形不等式不等號為 $\geq$ 時，若轉移方程取 min，那麼最優決策點的方向跟 $i$ 移動的方向相反
當四邊形不等式不等號為 $\geq$ 時，若轉移方程取 max，那麼最優決策點的方向跟 $i$ 移動的方向相同

容易發現其實這就只是排列組合而已，所以只要搞懂其中一個其他的就可以類推出來了。接下來我們只用第一個 case 來進行證明。而這也是整篇文章中唯二的第一個證明。

定理1證明

$dp_i=\min\{dp_j+w(i,j)\}$ $w(a,c)+w(b,d)\leq\ w(a,d)+w(b,c)$
第一個情形的轉移式和四邊形不等式如上。

要證明決策單調性就相當於證明 $p_i\leq p_{i+1}$
令 $p_i,p_{i+1}$ 代表 $dp_i,dp_{i+1}$ 的最優決策點，那麼我們有：
$dp_{p_i}+w(i,p_i)\leq dp_j+w(i,j)\ \forall j<i$ ..... 式 (1) $dp_{p_{i+1}}+w(i+1,p_{i+1})\leq dp_j+w(i+1,j)\ \forall j<i+1$ ...... 式(2)
以下分兩種情況討論：
$p_{i+1}=i$ ：因為 $p_i<i$ ，所以 $p_i\leq p_{i+1}$ 必定成立
$p_{i+1}\neq i$ ：將 (1) 的 $j$ 代入 $p_{i+1}$ ，(2) 的 $j$ 代入 $p_i$ 可以得到下面兩個式子： $dp_{p_i}+w(i,p_i)\leq dp_{p_{i+1}}+w(i,p_{i+1})$ $dp_{p_{i+1}}+w(i+1,p_{i+1})\leq dp_{p_i}+w(i+1,p_i)$ 把這兩個式子相加可以得到： $w(i,p_i)+w(i+1,p_{i+1})\leq w(i,p_{i+1})+w(i+1,p_i)$ 根據四邊形不等式可以利用反證證出 $p_i\leq p_{i+1}$ ，證畢。

那我們有決策單調性可以做什麼呢？我們剛剛提到了，單調隊列優化以及斜率優化都具有決策單調性，而他們確實也符合四邊形不等式。這部分就自己留給讀者證明，接下來這邊給出四邊形優化的一般型式：

四邊形不等式一般情形：分治/二分+資料結構

為了方便下文講解，以下一律考慮決策點單調遞增的情形。

單調隊列優化跟斜率優化都對 $w(i,j)$ 有比較特別的要求。具體來說，要可以把 $i,j$ 分離到一定程度。那麼如果 $w$ 只滿足四邊形不等式呢？舉例來說： $w(i,j)=-\sqrt{i+j}$ (關於為什麼他滿足四邊形不等式就繼續往下看ㄅ)。而即使 $dp$ 滿足最優決策點遞增，也沒辦法用類似單調隊列的方法快速求出 $dp(i)$ 。(考慮決策點永遠都是 $j=1$ 的情況，如此一來還是需要 $O(N^2)$ 的時間來處理。)

所以接下來我們要介紹兩個如果 $w$ 滿足四邊形不等式的通用作法：

分治優化 (四邊形不等式篇)

修但幾類，為什麼分治優化會出現在這邊？難不成分治優化也跟四邊形優化有關？我們這邊給出我所知道的分治優化的轉移式跟使用時機：

$dp(i,j)=\min\limits_{k<j}\{dp(i-1,k)+w(k,j)\}$
如果 DP 這個陣列滿足決策點單調，那麼可以使用分治優化：
決策點單調：令 $p(i,j)$ 為 $dp(i,j)$ 的最優決策點。
如果 $\forall i,j$ ，滿足 $p(i,j)\leq p(i,j+1)$ ，則稱之為決策點單調

這裡要先提一點，如果 $dp(i,j)$ 滿足決策點單調的話， $w(k,j)$ 不一定要滿足四邊形優化(因為決策點單調不能推回去四邊形不等式成立)。也就是說分治優化不一定需要滿足四邊形不等式(但作法是一樣的)。我們這邊說明滿足四邊形不等式的分治優化：

決策點單調？那不就是我們這章在講的內容嘛！但是我們現在只討論了 1D/1D DP 的決策點單調，那這個要怎麼處理呢？

可以發現一件事情，上面的這個轉移式的 $dp(i,j)$ 來源都是從 $dp(i-1,*)$ 來的，也就是說如果 $dp(i-1,*)$ 已經全部都處理完了，那麼 $dp(i,*)$ 其實就可以當成是從一坨跟 $i$ 完全沒有關係的東西轉移。那麼我們不妨就可以把上面這個轉移式改寫：

$dp(j)=\min\limits_{k<j}\{g(k)+w(k,j)\}$ ，而最佳決策點變成 $p(j)$

而分治優化其實就是在把上面這個轉移式做 $N$ 次而已。於是我們就把他變成 1D/1D DP 了。而我們又知道，如果 $g(k)+w(k,j)$ 滿足四邊形不等式，那麼 $dp(j)$ 的決策點單調，那我們就可以在分治優化上面套四邊形優化啦！而事實上我們有一件事情：如果 $g(j)+w(i,j)$ 滿足四邊形不等式，那麼 $w(i,j)$ 滿足四邊形不等式。(直接帶進四邊形不等式就顯然了)。又由於 $g,w$ 都是跟 $dp$ 無關的函數，我們可以把上面那個式子換一些符號重新整理一下：

$dp(i)=\min\limits_{j<i}\{w(i,j)\}$ ，其中 $w(i,j)$ 是一個跟 $dp$ 無關的函數，並且滿足四邊形不等式。

而只要滿足上面這個式子，我們可以考慮使用以下分治方法解決：

令 $solve(L,R,L',R')$ 函數代表對於 $dp(L)$ 到 $dp(R)$ 的 DP 值，在已知決策點落在 $[L',R']$ 的條件下求出 DP 值。首先我們先考慮 $mid=\frac{l+r}{2}$ ，我們先暴力枚舉 $[L',R']$ 求出 $dp(mid)$ 以及他的最優決策點。由決策單調性我們知道 $\forall j\in[L,mid)$ ， $p(j)\leq p(mid)$ ，並且 $\forall j\in(mid,R]$ ， $p(mid)\leq p(j)$ ，那麼我們就可以把這個問題拆成兩個子問題分治遞迴下去做了： $solve(L,mid-1,L',p[mid]),solve(mid+1,R,p[mid],R')$

於是我們就可以用 $O(NlogN)$ 的時間內解掉這題，回到原本分治優化的轉移式就只需要把這件事情做 $N$ 次，也就是 $O(N^2logN)$ 。

一個我在網路上看到的有趣的事，上述的作法其實就是 CDQ 分治的思想，所以在某些特別情況下可以使用 CDQ 分治來跟分治優化進行搭配。(但是由於 iceylemon 不太熟 CDQ 所以有興趣的讀者可以自行研究，如果會了歡迎來教我><)。

這裡給上分治優化的模板：

分治優化模板

void solve(int x, int l, int r, int ql, int qr) {
    if(l > r) return;
    int mid = (l + r) >> 1, p = 0;
    dp[x][mid] = 1e18;
    for(int i = ql; i <= min(qr, mid - 1); i ++) {
        if(dp[x][mid] >= dp[x - 1][i] + w(i,j)) {
            dp[x][mid] = dp[x - 1][i] + w(i,j);
            p = i;
        }
    }
    solve(x, mid + 1, r, p, qr);
    solve(x, l, mid - 1, ql, p);
}

分治優化類型題目

備註

事實上這個轉移式：

$dp(i,j)=\min\limits_{k<j}\{dp(i-1,k)+w(k,j)\}$

在 $w$ 滿足更特別的性質的時候可以把時間複雜度壓到 $O(N^2)$ ，在接下來 2D/1D 的地方會提到。

二分+資料結構

上面分治優化的部分滿足了一件事： $dp(i)$ 的取值不受其他 $dp$ 值的影響。而如果 $dp$ 的取值受前面其他 $dp$ 的影響呢？也就是：

$dp(i)=\min\limits_{j<i}\{dp(j)+w(i,j)\}$

這個時候就不能使用分治了，因為分治的過程中我們會先暴力的算出 $dp(mid)$ 才去遞迴算出其他 DP。而這個時候我們通常會使用二分搜+單調隊列/單調stack來優化這個問題。做法如下：

從這個章節開始到現在，我們所做的 DP 都是對於每個位置快速的求出最優決策點。而這個方法比較特殊，我們考慮的是對於每個位置，考慮他會成為哪些 DP 值的最優決策點。

由於滿足決策單調性，所以最優決策點是單調遞增的。所以我們的最優決策點陣列 $p$ 可能會長成下面這樣( $n=14$ )：

$p=00111222333336$

而進一步來說，因為遞增的緣故，於是我們可以用一個類似單調隊列的東西來維護這個陣列。我們使用一個 queue 來維護每個決策點 $i$ ，這個點是最優決策點的區間 $[l_i,r_i]$ 。舉例來說，上面那個 $p$ 可以被寫成：

$[(0,1,2),(1,3,5),(2,6,8),(3,9,13),(6,14,14)]$

這時候我們就可以變成維護這個單調隊列了。我們考慮依序枚舉決策點，當我們枚舉到 $i$ 的時候，我們想要知道 $i$ 這個決策點的左界會是誰，這個時候我們就可以對這個單調隊列做二分搜。如果一個位置他選擇 $i$ 當決策點的時候會比原本更好的話，就代表 $i$ 的左界在這個點的左邊。反之，如果一個位置選擇 $i$ 當決策點的時候不會比原本更好，那麼 $i$ 的左界就在這個點的右邊，或是 $i$ 不能成為任何人的最優決策點。

舉個例子說明實作過程：假設我們已經處理完上面那個情形決策點到 $i=2$ 的情形，現在要處理最優決策點為 $3$ 的情形，為了方便說明我們用陣列的形式來表示：

$p=00111222222222$

我們第一步先檢查 $n$ 的位置可不可以使用 $3$ 當最優決策點，如果不行的話，那麼 $3$ 就不可能成為任何位置的最優決策點。如果可以的話，我們先檢查這個隊列的最後一個區間是不是可以被 $3$ 完全取代掉。如果可以的話就先把他從隊列中移除。接著就對整個陣列(單調隊列)進行二分搜，找到 $3$ 的左界然後把他左界右邊的所有值都變成 $3$ ，於是經過操作後 $p$ 就變成：

$p=00111222333333$

一直重複這個過程就可以把整個最優決策點找出來了。而如果要求 $dp$ 的話，就直接使用這個最優決策點進行轉移即可。下面給出模板程式碼：

1D/1D 四邊形優化模板

struct segment {
    int i, l, r;
};
int n, dp[maxn];
deque<segment> dq;

inline int w(int l, int r) {
    // return a value
}

void solve() {
    dq.clear();
    dq.push_back({0, 1, n});
    for(int i = 1; i <= n; i ++) {
        // 把"過期"的區間pop掉
        while(dq.front().r < i) dq.pop_front();
        // 先得到dp[i]
        dp[i] = dp[dq.front().i] + w(dq.front().i, i);
        // 完全無法加入
        segment t = dq.back();
        if(dp[t.i] + w(t.i, n) < dp[i] + w(i, n)) {
            continue;
        }
        // 先移除掉會被i完全取代掉的區間
        while(!dq.empty()) {
            segment t = dq.back();
            if(i < t.l and dp[t.i] + w(t.i, t.l) > dp[i] + w(i, t.l)) {
                dq.pop_back();
            }
            else break;
        }
        // 特判全部被移掉的情形
        if(dq.empty()) {
            dq.push_back({i, i + 1, n});
            continue;
        }
        // 開始進行二分搜
        segment tmp = dq.back();
        int x = tmp.i, l = tmp.l, r = n, ans = n;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(dp[x] + w(x, mid) > dp[i] + w(i, mid)) {
                r = mid - 1;
                ans = min(ans, mid);
            }
            else l = mid + 1;
        }
        dq.pop_back();
        if(ans - 1 >= tmp.l) dq.push_back({tmp.i, tmp.l, ans - 1});
        dq.push_back({i, ans, n});
    }
}

上面的做法是使用單調隊列來進行優化，如果不等號改向的可以同理使用單調stack來優化即可。

其實上面分治的作法也可以使用這個方法去實作，但是這個方法有一個缺陷，那就是如果單個 $w$ 的計算複雜度高的話，那麼就會二分搜的複雜度就會退化。

但是如果 $w$ 可以透過上一個計算出來的 $w'$ 快速的推導出來，那麼分治法可以解決這個類型的問題。(當然， $dp$ 的值還是不能互相影響)。上述 CF 868F 這題就只能使用分治去做。

四邊形優化題目

2D/1D DP 與四邊形不等式

除了 1D/1D DP 之外，某些類型的 2D/1D DP 也可以套用四邊形優化。

假設有一個 DP 方程長的像下面這兩個樣子(分別叫他們式(1), 式(2))：

$dp(l,r)=\min\limits_{k<j}\{dp(l,k)+dp(k+1,r)+w(l,r)\}$

$dp(i,j)=\min\limits_{k<j}\{dp(i-1,k)+w(k+1,j)\}$ (這個就是上面分治優化的轉移式)

如果 $w$ 滿足四邊形不等式以及區間單調性，那麼我們可以在 $O(N^2)$ 的時間內解決這兩個問題。

區間單調性：即 $\forall a,b,c,d,\ a\leq b\leq c\leq d, w(a,d)\geq w(b,c)$

這裡也就是說一個區間會比他包含的子區間的 $w$ 值還要大。值得注意的是，因為我們一直都只有討論四邊形一個方向的不等號，如果四邊形不等式的不等號變號的話，這裡的區間單調性也要跟著變號。

我們要怎麼把他優化成 $O(N^2)$ 呢？我們這邊引入兩個引理：

對於上述 DP 式，如果 $w$ 滿足四邊形不等式以及區間單調性，那麼 $dp$ 也滿足四邊形不等式
如果 $dp$ 滿足四邊形不等式，令 $p(l,r)$ 代表 $dp(l,r)$ 的最優決策點，則有： $p(l,r-1)\leq p(l,r)\leq p(l+1,r)$

關於證明的部分我個人覺得不太重要，如果想知道的可以左轉這篇。

然而有了上面這兩個引理我們就可以想到一個做法：

每次處理 $dp(l,r)$ 的時候我們只需要枚舉 $[p(l,r-1),p(l+1,r)]$ 這個區間來找到 dp 的值以及他的最優決策點就可以了。

上面這個作法其實是 $O(N^2)$ 的，這邊給出本章節的唯二個證明(只證明第一式)：

因為這個東西就是一個類似區間DP，所以我們一樣用區間DP的想法去看：
枚舉每一個區間長度 $len$ ，對於每一個左端點 $l$ ：
$l=1$ ，區間 $[l,l+len-1]$ 的枚舉長度為 $p_{2,len}-p_{1,len-1}$ $l=2$ ，枚舉長度為 $p_{3,len+1}-p_{2,len}$ ... ... $l=n+1-len$ ，枚舉長度為 $p_{n+2-len,n}-p_{n+1-len,n-1}$
把上面的式子全部相加，消一消之後就變成： $p_{n+2-len,n}-p_{1,len-1}\leq n$ 而 $len$ 總共只有 $n$ 種取值，所以複雜度為 $O(N^2)$

至此我們也解決了 2D/1D 的問題。而我們也給出了在滿足區間單調性的條件下，式(2) 甚至可以達到 $O(N^2)$ 的複雜度。而值得注意的是，如果 $w$ 沒辦法快速計算的話，這個方法的複雜度一樣會退化。所以還是需要考慮使用分治優化。在實際運用上需要多加注意。

題目

Atcoder DP Contest N
IOI 2000 郵局
CF 321E 上面出現過了，這邊再出現一次

四邊形不等式小知識

這裡給出一些四邊形不等式你需要知道的事情，這個部分的證明不會太難，證明的部分就自己想一下囉。

$\forall i<j$ ， $w(i,j)+w(i+1,j+1)\leq w(i+1,j)+w(i,j+1)$ 跟 $w$ 滿足四邊形不等式是等價條件。
在 2D/1D DP 的部分我們寫了 $p(i,j-1)\leq p(i,j)\leq p(i+1,j)$ ，整理一下之後可以變成 $p(i-1,j)\leq p(i,j)\leq p(i,j+1)$ 。寫成這個形式可以讓你枚舉的時候方便一點。

滿足四邊形不等式的函數

四邊形優化最難的地方就是看出他滿足四邊形不等式。在競賽中我們可以試著用打表的方式來驗證他是否滿足，但是這邊還是介紹一些簡單的規則來方便判斷一個函數是否滿足四邊形不等式：

$w(i,j)=f(i)+g(j)$ 也就是 $w$ 可以被拆成只由 $i$ 項組成的函數跟 $j$ 項組成的函數相加。
如果存在兩個函數 $w_1(i,j),w_2(i,j)$ 皆滿足四邊形不等式，那麼對於任意實數 $c_1,c_2\geq 0$ ， $c_1w_1+c_2w_2$ 也滿足四邊形不等式。
令 $h(x)$ 是一個單調遞增的凸函數(convex)。若 $w(i,j)$ 滿足四邊形不等式並且具有區間單調性，那麼 $h(w(i,j))$ 也滿足四邊形不等式以及區間單調性。

你們想要看證明嗎？其實我不想講證明(x 前兩個的證明是顯然的，直接帶回原本的四邊形不等式就可以了。而第三個的證明有點複雜，我覺得會用比較實在。如果有興趣的讀者可以前往 OI Wiki 欣賞證明。

參考資料

Previous斜率優化 (Convex Hull Trick)NextAliens 優化

Last updated 3 years ago

Was this helpful?

概述

1D/1D DP 與 決策單調性