斜率優化

例題引入

「HNOI2008」玩具裝箱

有 \(n\) 個玩具，第 \(i\) 個玩具價值為 \(c_i\)。要求將這 \(n\) 個玩具排成一排，分成若干段。對於一段 \([l,r]\)，它的代價為 \((r-l+\sum_{i=l}^r c_i-L)^2\)。其中 \(L\) 是一個常量，求分段的最小代價。

\(1\le n\le 5\times 10^4, 1\le L, c_i\le 10^7\)。

樸素的 DP 做法

令 \(f_i\) 表示前 \(i\) 個物品，分若干段的最小代價。

狀態轉移方程：\(f_i=\min_{j<i}\{f_j+(i-(j+1)+pre_i-pre_j-L)^2\}=\min_{j<i}\{f_j+(pre_i-pre_j+i-j-1-L)^2\}\)。

其中 \(pre_i\) 表示前 \(i\) 個數的和，即 \(\sum_{j=1}^i c_j\)。

該做法的時間複雜度為 \(O(n^2)\)，無法解決本題。

優化

考慮簡化上面的狀態轉移方程式：令 \(s_i=pre_i+i,L'=L+1\)，則 \(f_i=\min_{j<i}\{f_j+(s_i-s_j-L')^2\}\)。

將與 \(j\) 無關的移到外面，我們得到

\[ f_i - (s_i-L')^2=\min_{j<i}\{f_j+s_j^2 + 2s_j(L'-s_i) \} \]

考慮一次函數的斜截式 \(y=kx+b\)，將其移項得到 \(b=y-kx\)。我們將與 \(j\) 有關的信息表示為 \(y\) 的形式，把同時與 \(i,j\) 有關的信息表示為 \(kx\)，把要最小化的信息（與 \(i\) 有關的信息）表示為 \(b\)，也就是截距。具體地，設

\[ \begin{aligned} x_j&=s_j\\ y_j&=f_j+s_j^2\\ k_i&=-2(L'-s_i)\\ b_i&=f_i-(s_i-L')^2\\ \end{aligned} \]

則轉移方程就寫作 \(b_i = \min_{j<i}\{ y_j-k_ix_j \}\)。我們把 \((x_j,y_j)\) 看作二維平面上的點，則 \(k_i\) 表示直線斜率，\(b_i\) 表示一條過 \((x_j,y_j)\) 的斜率為 \(k_i\) 的直線的截距。問題轉化為了，選擇合適的 \(j\)（\(1\le j<i\)），最小化直線的截距。

slope_optimization

如圖，我們將這個斜率為 \(k_i\) 的直線從下往上平移，直到有一個點 \((x_p,y_p)\) 在這條直線上，則有 \(b_i=y_p-k_ix_p\)，這時 \(b_i\) 取到最小值。算完 \(f_i\)，我們就把 \((x_i,y_i)\) 這個點加入點集中，以做為新的 DP 決策。那麼，我們該如何維護點集？

容易發現，可能讓 \(b_i\) 取到最小值的點一定在下凸殼上。因此在尋找 \(p\) 的時候我們不需要枚舉所有 \(i-1\) 個點，只需要考慮凸包上的點。而在本題中 \(k_i\) 隨 \(i\) 的增加而遞增，因此我們可以單調隊列維護凸包。

具體地，設 \(K(a,b)\) 表示過 \((x_a,y_a)\) 和 \((x_b,y_b)\) 的直線的斜率。考慮隊列 \(q_l,q_{l+1},\ldots,q_r\)，維護的是下凸殼上的點。也就是説，對於 \(l<i<r\)，始終有 \(K(q_{i-1},q_i) < K(q_i,q_{i+1})\) 成立。

我們維護一個指針 \(e\) 來計算 \(b_i\) 最小值。我們需要找到一個 \(K(q_{e-1},q_e)\le k_i< K(q_e,q_{e+1})\) 的 \(e\)（特別地，當 \(e=l\) 或者 \(e=r\) 時要特別判斷），這時就有 \(p=q_e\)，即 \(q_e\) 是 \(i\) 的最優決策點。由於 \(k_i\) 是單調遞減的，因此 \(e\) 的移動次數是均攤 \(O(1)\) 的。

在插入一個點 \((x_i,y_i)\) 時，我們要判斷是否 \(K(q_{r-1},q_r)<K(q_r,i)\)，如果不等式不成立就將 \(q_r\) 彈出，直到等式滿足。然後將 \(i\) 插入到 \(q\) 隊尾。

這樣我們就將 DP 的複雜度優化到了 \(O(n)\)。

概括一下上述斜率優化模板題的算法：

將初始狀態入隊。
每次使用一條和 \(i\) 相關的直線 \(f(i)\) 去切維護的凸包，找到最優決策，更新 \(dp_i\)。
加入狀態 \(dp_i\)。如果一個狀態（即凸包上的一個點）在 \(dp_i\) 加入後不再是凸包上的點，需要在 \(dp_i\) 加入前將其剔除。

接下來我們介紹斜率優化的進階應用，將斜率優化與二分/分治/數據結構等結合，來維護性質不那麼好（缺少一些單調性性質）的 DP 方程。

二分/CDQ/平衡樹優化 DP

當我們在 \(i\) 這個點尋找最優決策時，會使用一個和 \(i\) 相關的直線 \(f(i)\) 去切我們維護的凸包。切到的點即為最優決策。

在上述例題中，直線的斜率隨 \(i\) 單調變化，但是對於有些問題，斜率並不是單調的。這時我們需要維護凸包上的每一個節點，然後每次用當前的直線去切這個凸包。這個過程可以使用二分解決，因為凸包上相鄰兩個點的斜率是有單調性的。

玩具裝箱改

有 \(n\) 個玩具，第 \(i\) 個玩具價值為 \(c_i\)。要求將這 \(n\) 個玩具排成一排，分成若干段。對於一段 \([l,r]\)，它的代價為 \((r-l+\sum_{i=l}^r c_i-L)^2\)。其中 \(L\) 是一個常量，求分段的最小代價。

\(1\le n\le 5\times 10^4,1\le L\le 10^7,-10^7\le c_i\le 10^7\)。

本題與「玩具裝箱」問題唯一的區別是，玩具的價值可以為負。延續之前的思路，令 \(f_i\) 表示前 \(i\) 個物品，分若干段的最小代價。

狀態轉移方程：\(f_i=\min_{j<i}\{f_j+(pre_i-pre_j+i-j-1-L)^2\}\)。

其中 \(pre_i = \sum_{j=1}^i c_j\)。

將方程做相同的變換

\[ f_i - (s_i-L')^2=\min_{j<i}\{f_j+s_j^2 + 2s_j(L'-s_i) \} \]

然而這時有兩個條件不成立了：

直線的斜率不再單調；
每次加入的決策點的橫座標不再單調。

仍然考慮凸殼的維護。

在尋找最優決策點，也就是用直線切凸殼的時候，我們將單調隊列找隊首改為：凸殼上二分。我們二分出斜率最接近直線斜率的那條凸殼邊，就可以找到最優決策。

在加入決策點，也就是凸殼上加一個點的時候，我們有兩種方法維護。

第一種方法是直接用平衡樹維護凸殼。那麼尋找決策點的二分操作就轉化為在平衡樹上二分，插入決策點就轉化為在平衡樹上插入一個結點，並刪除若干個被踢出凸殼的點。此方法思路簡潔但實現繁瑣。

下面介紹一種基於 CDQ 分治的做法。

設 \(\text{CDQ}(l,r)\) 代表計算 \(f_i,i\in [l,r]\)。考慮 \(\text{CDQ}(1,n)\)：

我們先調用 \(\text{CDQ}(1,mid)\) 算出 \(f_i,i\in[1,mid]\)。然後我們對 \([1,mid]\) 這個區間內的決策點建凸殼，然後使用這個凸殼去更新 \(f_i,i\in [mid+1,n]\)。這時我們決策點集是固定的，不像之前那樣邊計算 DP 值邊加入決策點，那麼我們就可以把 \(i \in [mid+1,n]\) 的 \(f_i\) 先按照直線的斜率 \(k_i\) 排序，然後就可以使用單調隊列來計算 DP 值了。當然，也可以在靜態凸殼上二分計算 DP 值。
對於 \([mid+1,n]\) 中的每個點，如果它的最優決策的位置是在 \([1,mid]\) 這個區間，在這一步操作中他就會被更新成最優答案。當執行完這一步操作時，我們發現 \([1,mid]\) 中的所有點已經發揮了全部的作用，凸殼中他們存不存在已經不影響之後的答案更新。因此我們可以直接捨棄這個區間的決策點，並使用 \(\text{CDQ}(mid+1,n)\) 解決右區間剩下的問題。

時間複雜度 \(O(n\log^2 n)\)。

對比「玩具裝箱」和「玩具裝箱改」，可以總結出以下兩點：

二分/CDQ/平衡樹等能夠優化 DP 方程的計算，於一定程度上降低複雜度，但不能改變這個方程本身。
DP 方程的性質會取決於數據的特徵，但 DP 方程本身取決於題目中的數學模型。

小結

斜率優化 DP 需要靈活運用，其宗旨是將最優化問題轉化為二維平面上與凸包有關的截距最值問題。遇到性質不太好的方程，有時需要輔以數據結構來加以解決，屆時還請就題而論。

習題

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