SHARE
TWEET

四邊形不等式優化

pdpd123 Sep 22nd, 2019 244 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. \section{四邊形不等式優化}
  2.  
  3. 所謂四邊形不等式優化,就是俗稱的打表找規律優化。為什麼這樣稱呼呢?因為四邊形不等式優化的滿足條件難以一眼看出  ,有些題目更是難以證明。前國手波路特石曾經說過:「我在選訓二模的時候,看到一題dp,我猜它是四邊形,就用原始的dp式打表找規律,最後AC了。」沒錯,四邊形不等式優化就是那麼玄妙的東西。
  4.  
  5. \subsection{四邊形不等式與四邊形單調性}
  6.  
  7. 四邊形不等式優化之所以可以對轉移進行加速,是建立在\textbf{四邊形單調性}的基礎上。四邊形單調性是一個雙變數函數的性質,分為凹凸兩種。\\
  8.  
  9. \definition{四邊形單調性}{
  10.     函數$F$滿足\textbf{凹四邊形單調性},若對於任意的$i<i', j<j'$:\\
  11.     如果$F(j, i) \leq F(j', i)$成立的話,必可以保證$F(j, i') \leq F(j', i')$。\\
  12.  
  13.     函數$F$滿足\textbf{凸四邊形單調性},若對於任意的$i<i', j<j'$:\\
  14.     如果$F(j, i) \geq F(j', i)$成立的話,必可以保證$F(j, i') \geq F(j', i')$
  15. }
  16.  
  17. 我們可以把$i$想像成時間,若$i$越大則越接近未來。那麼就可以把凹四邊形單調性想成:若此時(時刻$i$)的$j$$j'$小,那未來(時刻$i'$)永遠都是$j$比較小。凸四邊形單調也可以用同樣的方式想:若此時$j$$j'$大,那未來永遠都是$j$比較大。\\
  18.  
  19. 由於當你看到一個函數$F$時,你很難看出這個到底有沒有四邊形單調性,所以我們很常使用\textbf{四邊形不等式}來判斷這個函數的四邊形單調性。\\
  20.  
  21. \definition{四邊形不等式}{
  22.     \textbf{凹四邊形不等式:}\\
  23.     如果對於任何$ i < i' \leq  j < j'$ 都有 $F(j, i) + F(j', i') \geq F(j, i') + F(j', i)$,則 $F$ 滿足凹四邊
  24. 形單調性。\\
  25.  
  26.     \textbf{凸四邊形不等式:}\\
  27.     如果對於任何$ i < i' \leq  j < j'$ 都有 $F(j, i) + F(j', i') \leq F(j, i') + F(j', i)$,則 $F$ 滿足凸四邊
  28. 形單調性。\\
  29.  
  30.     如果這邊的$i, j$都是整數的話,我們只需要檢查$F(j, i) + F(j + 1, i + 1)$$F(j, i + 1) + F(j + 1, i)$ 的大小關係即可。
  31. }
  32.  
  33. 滿足四邊形不等式的條件又稱為Monge condition,若一個函數滿足凸四邊形不等式,則必滿足凸四邊形單調性;若一個函數滿足凹四邊形不等式,則必滿足凹四邊形單調性。但是不滿足四邊形不等式的函數不一定沒有四邊形單調性,所以這時候,打表就是你的好幫手了。\\
  34.  
  35. \problem{四邊形單調性}{
  36.     數學題 - 判斷下列函數是否有凹四邊形單調性:
  37.     \begin{enumerate}
  38.     \item $F(x, y) = xy$
  39.     \item $F(x, y) = (x-y)^2$
  40.     \item $F(x, y) = s_x - t_y$$s, t$是遞增數列
  41.     \item $F(x, y) = (s_x - s_y)^2$$s$是遞增數列
  42.     \item $F(x, y) = aA(x, y) + bB(x, y)$$a, b \geq 0$$A, B$有凹四邊形單調性
  43.     \item $F(x, y) = (x - y - 1 - K + \sum\limits_{k=x+1}^y C_k)^2$$C$是正整數數列,$K$是正整數
  44.     \item $F(x, y) = -a_x + a_y - \sqrt{y-x}$$a$是正整數數列
  45.     \end{enumerate}
  46. }
  47.  
  48. \subsection{1D/1D 凸性優化}
  49.  
  50. 這邊要先來個簡單的名詞定義。如果我們說一個dp是$eD/tD$的,代表這個問題有$O(N^e)$個子問題,每個子問題需要$O(N^t)$的時間轉移,所以一個$eD/tD$的dp的總時間複雜度是$O(N^{e+t})$
  51.  
  52. \subsubsection{主要思維}
  53.  
  54. 說了這麼多,那四邊形單調性可以幹嘛呢?我們看看以下dp式:
  55.  
  56. \begin{displaymath}
  57. dp[i] = \min\limits_{0\leq j < i} \{dp[j] + w(j, i) \}
  58. \end{displaymath}
  59.  
  60. 這種類型的dp可說是再熟悉不過了,這就是枚舉分段點再加上cost的題型。我們令$F(j, i) = dp[j] + w(j, i)$,如此一來我們在計算每個$dp[i]$時事實上就是在找$F(j, i)$最小的$j$。\\
  61.  
  62. 如果知道$w(j, i)$滿足凸四邊形單調性,那麼$F(i, j)$也會具備凸四邊形單調性,於是就可以套用四邊形不等式優化。\\
  63.  
  64. 1D/1D四邊形不等式凸性優化的精髓在於:如果在某個$i$時,$F(j, i)$$F(j', i)$大(這裡的$j < j'$),那麼對於所有的時刻$i < i'$永遠都是$F(j, i)$會比較大,所以只要有一時刻從$j'$轉移比從$j$轉移好,就會導致不管未來何時,$j'$一定比$j$好,所以就可以永遠不用從$j$轉移了。\\
  65.  
  66. \hint{
  67.     我們可以得到一個結論:\\
  68.     對於所有$i < i'$$dp[i]$$dp[i']$的最佳轉移來源$p_i \leq p_{i'}$
  69. }
  70.  
  71. 我們引述一句蕭電的話:\\
  72.  
  73. \eeric{
  74.     這與斜率優化的精神很像,就是限制轉移來源。斜率優化用的是斜率單調性,而四邊形則是隨著$i$的遞增,轉移點也會遞增。我們可以用這個遞增的性質來加速轉移過程。
  75. }
  76.  
  77. \subsubsection{實作方式}
  78.  
  79. 以下內容會有一些符號約定,這邊先列出來讓讀者更好理解:\\
  80. \definition{小約定}{
  81.     $i$:時間點,當時間點是$i$就代表你正在計算$dp[i]$的值。\\
  82.     $j$:轉移點,若我說時間點$i$$j=$某數字就代表$dp[i]$$j$那裡轉移。\\
  83.     $p$:最佳轉移點,$dp[i]$的最佳轉移點會寫成$p_i$。\\
  84.     $n$:就是$n$,也就是$i$的最大值。\\
  85.     如果出現$i, i', j, j'$,通常表示$i < i'$,而且$j < j'$
  86. }
  87.  
  88. 回歸到最原始的dp實作方式,我們在最外層的迴圈跑$i$,而內層迴圈枚舉轉移來源,看看哪個$j$可以使得$F(j ,i)$ 最小,來達到計算每個$dp[i]$的目的。\\
  89.  
  90. 現在套用了四邊形不等式優化,基本計算順序還是不變的,一樣是用一個迴圈跑$i$,逐步把$dp[i]$算出來。不過對於每個$i$都枚舉轉移來源$j$找最好的實在太慢了,就改成用集合維護一些區間,方便以$O(1)$查詢最佳的轉移來源。\\
  91.  
  92. 我們可以把區間$[1, n)$拆成許多不相交的小區間放進集合裡,集合裡的每個元素以$(p, L: R)$的方式儲存。若在時間點$i$時,集合裡面有元素$(p, L: R)$,就代表算到目前為止對於$L\leq i' < R$$i'$$dp[i']$的最佳轉移來源就是$p$,也就是說當$i$介於區間$[l, r)$內,則$F(p, i)$就會比其他$F(other j, i)$來的小。\\
  93. 那麼我們要怎麼維護這個集合呢?我們考慮以下演算法:
  94. \begin{enumerate}
  95. \item 一開始除了$dp[0]$沒有任何$dp[i]$被算出來,所以區間$[1, n)$目前能確定的最佳轉移來源只能是$0$,因此先在集合裡放入區間$(0, 1: n)$
  96. \item 當要計算$dp[i]$時,先把右界$R \leq i$的區間從集合中移除(因為這些區間已經不會再被用到了),然後再取右界最小的區間(此區間必包含$i$),從這個區間的$p$處轉移計算$dp[i]$
  97. \item 當你計算出了$dp[i]$,那麼之後某些$dp[i']$的最佳轉移來源有可能因此更新成了$i$。這時候因為我們知道$i'$變大時$p_{i'}$只可能不變或變大,所以可以找到一個點$i^*$,使得所有大於等於$i^*$$i'$的最佳轉移來源統統變成$i$
  98. \item 找到這個$i^*$的方法如下:我們考慮右界最大的區間$(p_f, L_f: R_f)$
  99. \begin{enumerate}
  100. \item$F(i, L_f) \leq F(p_f, L_f)$,則這個區間的最佳轉移來源都即將被$i$取代,所以可以直接將區間拔掉,再考慮右界第二大的區間。
  101. \item$F(i, R_f) \geq F(p_f, R_f)$,恭喜你,什麼事都不用做,因為$p_f$目前還是最好的。
  102. \item 如果不是上述兩種情況,必然能在這個區間裡找到$i^*$,我們只要二分搜找到$F(i, k) < F(p_f, k)$的最小$k$,就是$i^*$。再從這個$i^*$將區間切成兩段$(p_f, L_f, i^*)$$(i, i^*: n)$即可。
  103. \end{enumerate}
  104. \end{enumerate}
  105.  
  106. 由於這些步驟每次只需要取得右界最大或右界最小的區間,並且放入區間時只會改變到右界最大的區間,所以可以用\inline{deque}來維護這個集合。\\
  107.  
  108. 實作方式與細節如下:(感謝baluteshih)\\
  109.  
  110. \begin{C++}
  111. struct seg{int p,l,r;};
  112. deque<seg> deq;
  113. void solve(){
  114.    deq.push_back(seg{0,1,n});
  115.    for(int i=1; i<n; i++){
  116.        // 計算dp[i]
  117.        while(deq.front().r <= i) deq.pop_front();
  118.        dp[i] = f(deq.front().p, i);
  119.        // 更新以 i 作為轉移來源的區間
  120.        while(deq.size() &&
  121.          f(i, deq.back().l) < f(deq.back().p, deq.back().l))
  122.        deq.pop_back();
  123.        seg new_seg = seg{i, i+1, n};
  124.        if(deq.size()){ // 有可能全部被 pop 掉
  125.            int c = binary_search(deq.back().p, i);
  126.            // c 是滿足 f(i, k) < f(deq.back().i, k) 的最小 k
  127.            deq.back().r = new_seg.l = c;
  128.        }
  129.        if(new_seg.l < n) deq.push_back(new_seg);
  130.    }
  131. }
  132. \end{C++}
  133.  
  134. 當然,你要先確定你的函數$F$有凸四邊形單調性。
  135.  
  136. \subsection{1D/1D 凹性優化}
  137.  
  138. 凹性優化的題目十分罕見,不過還是有凹性優化的實作方式。\\
  139.  
  140. 與凸性優化的概念一樣,只不過相較於凸單調性,凹單調性可以推知:對於所有$i < i'$$dp[i]$$dp[i']$的最佳轉移來源$p_i \geq p_{i'}$。\\
  141.  
  142. 所以我們可以把凸性優化的\inline{deque}改成用\inline{stack}維護,top處放右界最小的區間,計算$dp$值時從top處pop掉不會再被用到的區間,然後選擇右界最小的區間轉移,每算完一個$dp[i]$,一樣從top處慢慢pop,再用二分搜找到$i^*$,不過因為是凸單調性,所以這裡的區間要拆成$(i+1, i^*)$$(i^*, L_f)$兩部分。\\
  143.  
  144. 實作細節與凸性優化差不多,這邊就不列code了。
  145.  
  146. \subsection{2D/1D 凸性優化}
  147.  
  148. 2D/1D 就是狀態二維,但轉移只有一維的dp,一般來說會長這樣:
  149.  
  150. \begin{displaymath}
  151. dp[i][j] = \min\limits_{i\leq k\leq j} \{ dp[i][k] + dp[k][j] + w(i, j) \}
  152. \end{displaymath}
  153.  
  154. 這邊與1D/1D一樣,假設$w(i, j)$符合凸四邊形單調性,那麼通常$dp[i][j]$就滿足凸四邊形單調性。所以這邊可以枚舉$i$,讓dp狀態變成一維,就可以用$N$次的1D/1D解決,時間複雜度$N^2\log n$。\\
  155.  
  156. \hint{如果 $w(i, j)$ 為凸單調性的且 $w(i, i + 2) \geq \max(w(i, i + 1), w(i + 1, i + 2))$,則 $dp[i][j]$ 也會符合凸單調性}
  157.  
  158. 2D/1D凸性優化還有一個神奇的性質,不僅可以增加效率、降低時間複雜度,還可以大大的減低實作難度。\\
  159.  
  160. 這邊要介紹一個定理:\\
  161.  
  162. \theorem{2D/1D 凸性優化}{
  163.     則設 $p_{i,j}$$dp[i][j]$ 在轉移時所找到的最佳轉移點,且 $dp$ 滿足凸四邊形不等式,則:
  164.     \begin{displaymath}
  165.     p_{i, j − 1} \leq p_{i, j} \leq p_{i + 1, j}
  166.     \end{displaymath}
  167. }
  168.  
  169. 神奇的證明如下:先假設$p_{i, j-1} = k_1$$p_{i, j} = u$$p_{i+1, j} = k_2$,我們使用反證法,分兩邊討論:
  170.  
  171. \begin{enumerate}
  172. \item 假設$k_1 > u$,則 $u+1 < k_1+1 \leq r-1 < r $,根據四邊形不等式可以得到:
  173. \begin{displaymath}
  174. dp[u+1][r-1] + dp[k_1+1][r] \leq dp[u+1][r] + dp[k_1+1][r-1]
  175. \end{displaymath}
  176. 再利用$u$$dp[i][j]$的最佳轉移來源的性質,可以列出以下式子:
  177. \begin{displaymath}
  178. dp[l][u] + dp[u+1][r] \leq dp[l][k_1] + dp[k_1+1][r]
  179. \end{displaymath}
  180. 將以上兩不等式相加,可得:
  181. \begin{displaymath}
  182. dp[l][u] + dp[u+1][r-1] \leq dp[l][k_1] + dp[k_1+1][r-1]
  183. \end{displaymath}
  184. 但這樣一來$k_1$就不是$p_{i, j-1}$了(因為選$u$的話更好),所以$k_1 \leq u$
  185.  
  186. \item 再假設$u > k_2$,可以用同樣方法,利用 $l < l+1 \leq k_2 < u $,列出四邊形不等式,再用$k_2$$dp[l+1][r]$的最佳轉移來源,列出$dp$$k_2$轉移與從$u$轉移的比較,最後再將兩不等式相加,就可以推出$u \neq p_{i, j}$的矛盾,因此$u \leq k_2$
  187. \end{enumerate}
  188.  
  189. 如此一來我們得到了$k_1 \leq u \leq k_2$,定理得證。
  190.  
  191. \subsubsection{實作}
  192.  
  193. 根據上述定理,我們可以發現到:$dp[i][j]$ 的轉移來源可以從區間 $[p_{i,j−1}, p_{i+1,j} ]$ 這個區間內找到,如果我們先計算$i-j$較小的$dp[i][j]$,並且記錄最佳的轉移點的話,枚舉範圍縮小了,就可以減少許多枚舉時間。\\
  194.  
  195. 那麼總共會省多少時間呢?我們可以考慮計算完一個 dp 表格的斜排 (也就是 $j - i$ 固定) 所需的時間:
  196.  
  197. \begin{displaymath}
  198. \vdots
  199. \end{displaymath}
  200. \begin{displaymath}
  201. p_{i−2,j−3} \leq p_{i−2,j−2} \leq p_{i−1,j−2}
  202. \end{displaymath}
  203. \begin{displaymath}
  204. p_{i−1,j−2} \leq p_{i−1,j−1} \leq p_{i,j−1}
  205. \end{displaymath}
  206. \begin{displaymath}
  207. p_{i,j−1} \leq p_{i,j} \leq p_{i+1,j}
  208. \end{displaymath}
  209. \begin{displaymath}
  210. p_{i+1,j} \leq p_{i+1,j+1} \leq p_{i+2,j+1}
  211. \end{displaymath}
  212. \begin{displaymath}
  213. p_{i+2,j+1} \leq p_{i+2,j+2} \leq p_{i+3,j+2}
  214. \end{displaymath}
  215. \begin{displaymath}
  216. \vdots
  217. \end{displaymath}
  218.  
  219. 看出來了嗎?中間那行是同一個斜排的不同$dp[i][j]$的轉移來源,這些轉移來源的區間正好是連續的並且這些轉移來源會隨著$i$遞增而遞增,所以計算一個斜排所需的時間僅僅是$O(N)$!一個狀態2D的dp表格頂多$O(N)$個斜排,所以總時間複雜度$O(N^2)$!\\
  220.  
  221. 這邊是2D/1D凸性優化的核心代碼:\\
  222.  
  223. \begin{C++}
  224. for(int len = 2; len <= n; len++){  // 枚舉區間長度 (i - j)
  225.    for(int i = 1, r = len; r <= n; i++, r++){
  226.        // 枚舉長度為 len 的所有區間
  227.        dp[i][j] = INF;
  228.        for (int k = p[i][j-1]; k <= p[i+1][j]; k++)
  229.            if (dp[i][j] > dp[i][k] + dp[k+1][j] + w(i, j)){
  230.            // 更新 dp 陣列
  231.            dp[i][j] = dp[i][k] + dp[k+1][j] + w(i, j);
  232.            p[i][j] = k;  // 記錄(最小)轉移來源
  233.        }
  234.    }
  235. }
  236. \end{C++}
  237.  
  238. \subsection{2D/1D 凹性優化}
  239.  
  240. 凹性沒有好性質 QQ\\
  241.  
  242. 所以只能枚舉$i$,讓dp狀態變成一維,用$N$次的1D/1D解決了。時間複雜度$N^2\log n$
  243.  
  244. \subsection{習題}
  245.  
  246. 待補 QQ
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top