不常見的DP優化 - Slope Trick | 山姆的競程日記

何謂 Slope Trick

Slope Trick的誕生大概是 Codeforces 713C - Sonya and Problem Wihtout a Legend 這個題目所衍生出來的一種 DP 優化方式。

他可以處理與凹凸性函數代價的 DP 優化，不過我也是在寫 CSES 時才知道這個 DP 優化技巧

Codeforces 713C

給你一個 \(n\) 項的陣列 \(A\)，每一次操作可以將一個元素 +1 或 -1，問最少要花費幾次操作才能使得整個陣列嚴格遞增?

測資範圍: \(1 \le n \le 3000\)

這個問題由於嚴格遞增的條件，不好處理，因此我們可以將 \(a_i := a_i - i\)

而經過這樣的變化之後，這個問題就變為了

給你一個 \(n\) 項的陣列 \(A\)，每一次操作可以將一個元素 +1 或 -1，問最少要花費幾次操作才能使得整個陣列非嚴格遞增?

藉由這個問題，我們可以很簡單的寫出一條 dp 的狀態式

先開另外一個陣列 \(B\)，為陣列 \(A\) 的元素經過排序與離散化後的結果

設 \(dp[i][j]\) 為將陣列前 \(i\) 個元素變為非嚴格遞增，並且 \(a_i \le b_j\) 所需要花的代價

轉移式十分簡單，也就是 \(dp[i][j] = \min(dp[i][j-1], dp[i-1][j] + |a_i-b_j|)\)

而這樣我們就可以在 \(O(n^2)\) 的時間解決這個問題了

能不能再更快?

答案是可以! ~~不然也不會有這篇文了~~

而我們就要去使用 Slope Trick 這個技巧來達到這件事情

可以做 Slope Trick 的函數

我們定義函數 \(f(x)\) 為可以做 Slope Trick 的函數 (接下來會簡稱為 Slope Trickable 函數)時，則他必須滿足

\(f(x)\) 必須是連續函數
\(f(x)\) 可以被分割為不同部分，且每個部份都是線性的，有各自的斜率
\(f(x)\) 必須是凸函數(Convex) 或凹函數(Concave)

而最經典的例子即為 \(f(x) = |x|\)

我們可以將其寫為一個分段函數

\[f(x) = \begin{cases}-x & \text{when } x < 0 \\ x & \text{when } 0 \le x\end{cases}\]

我們可以觀察到 \(f(x)\) 是連續的，而且可以被分割為多個線性函數，且 \(f(x)\) 是一個 凹函數

因此 \(f(x) = |x|\) 是一個Slope Trickable 函數

而我們可以將 \(f(x)\) 使用另外一種形式表達，\(f(x) = [y = x,S = \{0,0\}]\)

前面 \(y = x\) 表示這個函數最右邊的線性函數，而 \(S\) 表示的是斜率改變的點，我們稱這些點為分段點，每當在某一點 \(x\) 時斜率改變 \(1\) 時，在 \(S\) 裡面就要加入兩個 \(x\)

而從這個表示法，我們也可以很輕易的表達回原本的分段函數

藉由上面的這個範例，讓我們來看看另一個例子

\[f(x) = \begin{cases} -x+5 & \text{when } x < -1 \\ x+7 & \text{when } -1 \le x \le 2 \\ 3x+3 & \text{when } 2 \le x \end{cases}\]

我們可以觀察到 \(f(x)\) 是連續的，而且他是由多個線性函數所組成，且 \(f(x)\) 是一個凹函數

因此 \(f(x)\) 是一個Slope Trickable 函數

而我們可以將 \(f(x)\) 表示為 \(f(x) = [y=3x+3,S=\{-1,-1,2,2\}]\)

Slope Trickable 函數的可合併性

藉由 Slope Trickable 函數的定義，我們可以觀察到，對於兩個 Slope Trickable 函數 \(f(x)\) 和 \(g(x)\)，\(h(x) = f(x)+g(x)\) 依然為 Slope Trickable 函數，且 \(S_{h} = S_{f} \cup S_{g}\)

想法:

對於兩個連續函數 \(f(x)\) 與 \(g(x)\)， \(h(x) = f(x) + g(x)\) 依然連續

對於兩個可以被分割為多個線性函數的 \(f(x)\) 與 \(g(x)\)，\(h(x) = f(x)+g(x)\) 同樣可以被分隔為多個線性函數，且 \(f\) 與 \(g\) 分割點可以聯集成 \(h\) 的分割點

對於兩個凹函數或凸函數 \(f(x)\) 與 \(g(x)\)，相加之後 \(h(x) = f(x)+g(x)\) 仍然為凹函數或凸函數。

經由以上幾個性質，我們就可以來解決上面這個問題的優化了!

加速 \(O(n^2)\) DP!

回到原本的問題

給你一個 \(n\) 項的陣列 \(A\)，每一次操作可以將一個元素 +1 或 -1，問最少要花費幾次操作才能使得整個陣列非嚴格遞增?

首先，我們定義函數 \(dp_i(x)\) 表示將前 \(i\) 個元素變為非嚴格遞增，且 \(a_i \le x\) 的最小花費

我們可以利用數學歸納法證明 \(dp_i(x)\) 是 Slope Trick 函數

想法如下:

在 \(i=0\) 時，很顯然地 \(dp_0(x) = 0\)
假設在 \(i-1\) 時 \(dp_{i-1}(x)\) 是一個 Slope Trick 函數，我們額外定義一個函數 \(f_{i}(x)\) 表示將前 \(i\) 個元素變為非嚴格遞增，且 \(a_i = x\) 的最小花費。則 \(f_i(x) = dp_{i-1}(x) + |x-a_i|\)，我們可以觀察到 \(\displaystyle dp_i(x) = \min_{0 \le y \le x}f_i(y)\)，由於 \(|x-a_i|\) 是一個 Slope Trickable 函數，因此 \(f_i(x)\) 和 \(dp_i(x)\) 也都是 Slope Trickable 函數
由於我們上面提過，\(|x-a_i|\) 是一個 Slope Trickable 函數，且他的分段點是 \(\{a_i,a_i\}\)，因此 \(f_i(x)\) 的分段點為 \(S_{dp_{i-1}} \cup \{a_i,a_i\}\)

既然知道 \(f_i(x)\) 的分段點了，那 \(dp_i(x)\) 的分段點呢?

很簡單! 我們可以用一張圖來觀察 \(f_i(x)\)

既然是這樣，那如果我們要看 \(dp_i(x)\) 呢，他會長這樣

沒有錯! 他其實只是將斜率大於 \(0\) 的分段點 pop 掉!

也就是說，當我們的 \(x\) 大於所有分段點時，根據這題的想法，斜率會是 \(1\)

因此，這題的做法就是開一個 max heap/multiset 維護所有的分段點，並且每次去遍歷元素 \(a_i\) 時，在 heap/multiset 中加入 \(\{a_i,a_i\}\) (就會得到 \(S_{f_i}\))，並將答案加上 \(|\)最右邊的分割點(heap 中的最大值) - \(a_i|\) (因為 \(f_i(x) = dp_{i-1}(x)+|x-a_i|\))，然後將最大點 pop 掉 (得到 \(dp_i(x)\))，這樣就完成了!

因此 \(dp_i(x)\) 用 Slope Trickable 函數的表示法即為 \(dp_i(x) = [y = a, S]\)，而 a 就是所有的 \(|\)最右邊的分割點 - \(a_i|\) 的總和

而答案就會是 \(dp_n(\infty)\)，時間複雜度: \(O(n \log n)\)

參考程式碼如下

priority_queue<int> slope;
int ans = 0;

for(int i = 1;i <= n;i++){
    int x;
    cin >> x;
    slope.push(x);
    slope.push(x);
    ans += slope.top()-x;
    slope.pop();
}

可以去 CSES - Increasing Array II 丟丟看自己的解