API tools faq
paste
Advertisement
pdpd123

四邊形不等式優化

pdpd123
Sep 22nd, 2019
429
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Latex 13.54 KB | None | 0 0
raw download clone embed print report
  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)$來的小。\\
  94. 那麼我們要怎麼維護這個集合呢？我們考慮以下演算法：
  96. \begin{enumerate}
  97. \item 一開始除了$dp[0]$沒有任何$dp[i]$被算出來，所以區間$[1, n)$目前能確定的最佳轉移來源只能是$0$，因此先在集合裡放入區間$(0, 1: n)$。
  98. \item 當要計算$dp[i]$時，先把右界$R \leq i$的區間從集合中移除(因為這些區間已經不會再被用到了)，然後再取右界最小的區間(此區間必包含$i$)，從這個區間的$p$處轉移計算$dp[i]$。
  99. \item 當你計算出了$dp[i]$，那麼之後某些$dp[i']$的最佳轉移來源有可能因此更新成了$i$。這時候因為我們知道$i'$變大時$p_{i'}$只可能不變或變大，所以可以找到一個點$i^*$，使得所有大於等於$i^*$的$i'$的最佳轉移來源統統變成$i$。
  100. \item 找到這個$i^*$的方法如下：我們考慮右界最大的區間$(p_f, L_f: R_f)$
  101. \begin{enumerate}
  102. \item 若$F(i, L_f) \leq F(p_f, L_f)$，則這個區間的最佳轉移來源都即將被$i$取代，所以可以直接將區間拔掉，再考慮右界第二大的區間。
  103. \item 若$F(i, R_f) \geq F(p_f, R_f)$，恭喜你，什麼事都不用做，因為$p_f$目前還是最好的。
  104. \item 如果不是上述兩種情況，必然能在這個區間裡找到$i^*$，我們只要二分搜找到$F(i, k) < F(p_f, k)$的最小$k$，就是$i^*$。再從這個$i^*$將區間切成兩段$(p_f, L_f, i^*)$ 與 $(i, i^*: n)$即可。
  105. \end{enumerate}
  106. \end{enumerate}
  107.  
  108. 由於這些步驟每次只需要取得右界最大或右界最小的區間，並且放入區間時只會改變到右界最大的區間，所以可以用\inline{deque}來維護這個集合。\\
  109.  
  110. 實作方式與細節如下：(感謝baluteshih)\\
  111.  
  112. \begin{C++}
  113. struct seg{int p,l,r;};
  114. deque<seg> deq;
  115. void solve(){
  116.    deq.push_back(seg{0,1,n});
  117.    for(int i=1; i<n; i++){
  118.        // 計算dp[i]
  119.        while(deq.front().r <= i) deq.pop_front();
  120.        dp[i] = f(deq.front().p, i);
  121.        // 更新以 i 作為轉移來源的區間
  122.        while(deq.size() &&
  123.          f(i, deq.back().l) < f(deq.back().p, deq.back().l))
  124.        deq.pop_back();
  125.        seg new_seg = seg{i, i+1, n};
  126.        if(deq.size()){ // 有可能全部被 pop 掉
  127.            int c = binary_search(deq.back().p, i);
  128.            // c 是滿足 f(i, k) < f(deq.back().i, k) 的最小 k
  129.            deq.back().r = new_seg.l = c;
  130.        }
  131.        if(new_seg.l < n) deq.push_back(new_seg);
  132.    }
  133. }
  134. \end{C++}
  135.  
  136. 當然，你要先確定你的函數$F$有凸四邊形單調性。
  137.  
  138. \subsection{1D/1D 凹性優化}
  139.  
  140. 凹性優化的題目十分罕見，不過還是有凹性優化的實作方式。\\
  141.  
  142. 與凸性優化的概念一樣，只不過相較於凸單調性，凹單調性可以推知：對於所有$i < i'$，$dp[i]$與$dp[i']$的最佳轉移來源$p_i \geq p_{i'}$。\\
  143.  
  144. 所以我們可以把凸性優化的\inline{deque}改成用\inline{stack}維護，top處放右界最小的區間，計算$dp$值時從top處pop掉不會再被用到的區間，然後選擇右界最小的區間轉移，每算完一個$dp[i]$，一樣從top處慢慢pop，再用二分搜找到$i^*$，不過因為是凸單調性，所以這裡的區間要拆成$(i+1, i^*)$與$(i^*, L_f)$兩部分。\\
  145.  
  146. 實作細節與凸性優化差不多，這邊就不列code了。
  147.  
  148. \subsection{2D/1D 凸性優化}
  149.  
  150. 2D/1D 就是狀態二維，但轉移只有一維的dp，一般來說會長這樣：
  151.  
  152. \begin{displaymath}
  153. dp[i][j] = \min\limits_{i\leq k\leq j} \{ dp[i][k] + dp[k][j] + w(i, j) \}
  154. \end{displaymath}
  155.  
  156. 這邊與1D/1D一樣，假設$w(i, j)$符合凸四邊形單調性，那麼通常$dp[i][j]$就滿足凸四邊形單調性。所以這邊可以枚舉$i$，讓dp狀態變成一維，就可以用$N$次的1D/1D解決，時間複雜度$N^2\log n$。\\
  157.  
  158. \hint{如果 $w(i, j)$ 為凸單調性的且 $w(i, i + 2) \geq \max(w(i, i + 1), w(i + 1, i + 2))$，則 $dp[i][j]$ 也會符合凸單調性}
  159.  
  160. 2D/1D凸性優化還有一個神奇的性質，不僅可以增加效率、降低時間複雜度，還可以大大的減低實作難度。\\
  161.  
  162. 這邊要介紹一個定理：\\
  163.  
  164. \theorem{2D/1D 凸性優化}{
  165.     則設 $p_{i,j}$ 是 $dp[i][j]$ 在轉移時所找到的最佳轉移點，且 $dp$ 滿足凸四邊形不等式，則：
  166.     \begin{displaymath}
  167.     p_{i, j − 1} \leq p_{i, j} \leq p_{i + 1, j}
  168.     \end{displaymath}
  169. }
  170.  
  171. 神奇的證明如下：先假設$p_{i, j-1} = k_1$，$p_{i, j} = u$，$p_{i+1, j} = k_2$，我們使用反證法，分兩邊討論：
  172.  
  173. \begin{enumerate}
  174. \item 假設$k_1 > u$，則 $u+1 < k_1+1 \leq r-1 < r $，根據四邊形不等式可以得到：
  175. \begin{displaymath}
  176. dp[u+1][r-1] + dp[k_1+1][r] \leq dp[u+1][r] + dp[k_1+1][r-1]
  177. \end{displaymath}
  178. 再利用$u$是$dp[i][j]$的最佳轉移來源的性質，可以列出以下式子：
  179. \begin{displaymath}
  180. dp[l][u] + dp[u+1][r] \leq dp[l][k_1] + dp[k_1+1][r]
  181. \end{displaymath}
  182. 將以上兩不等式相加，可得：
  183. \begin{displaymath}
  184. dp[l][u] + dp[u+1][r-1] \leq dp[l][k_1] + dp[k_1+1][r-1]
  185. \end{displaymath}
  186. 但這樣一來$k_1$就不是$p_{i, j-1}$了(因為選$u$的話更好)，所以$k_1 \leq u$。
  187.  
  188. \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$。
  189. \end{enumerate}
  190.  
  191. 如此一來我們得到了$k_1 \leq u \leq k_2$，定理得證。
  192.  
  193. \subsubsection{實作}
  194.  
  195. 根據上述定理，我們可以發現到：$dp[i][j]$ 的轉移來源可以從區間 $[p_{i,j−1}, p_{i+1,j} ]$ 這個區間內找到，如果我們先計算$i-j$較小的$dp[i][j]$，並且記錄最佳的轉移點的話，枚舉範圍縮小了，就可以減少許多枚舉時間。\\
  196.  
  197. 那麼總共會省多少時間呢？我們可以考慮計算完一個 dp 表格的斜排 (也就是 $j - i$ 固定) 所需的時間：
  198.  
  199. \begin{displaymath}
  200. \vdots
  201. \end{displaymath}
  202. \begin{displaymath}
  203. p_{i−2,j−3} \leq p_{i−2,j−2} \leq p_{i−1,j−2}
  204. \end{displaymath}
  205. \begin{displaymath}
  206. p_{i−1,j−2} \leq p_{i−1,j−1} \leq p_{i,j−1}
  207. \end{displaymath}
  208. \begin{displaymath}
  209. p_{i,j−1} \leq p_{i,j} \leq p_{i+1,j}
  210. \end{displaymath}
  211. \begin{displaymath}
  212. p_{i+1,j} \leq p_{i+1,j+1} \leq p_{i+2,j+1}
  213. \end{displaymath}
  214. \begin{displaymath}
  215. p_{i+2,j+1} \leq p_{i+2,j+2} \leq p_{i+3,j+2}
  216. \end{displaymath}
  217. \begin{displaymath}
  218. \vdots
  219. \end{displaymath}
  220.  
  221. 看出來了嗎？中間那行是同一個斜排的不同$dp[i][j]$的轉移來源，這些轉移來源的區間正好是連續的並且這些轉移來源會隨著$i$遞增而遞增，所以計算一個斜排所需的時間僅僅是$O(N)$！一個狀態2D的dp表格頂多$O(N)$個斜排，所以總時間複雜度$O(N^2)$！\\
  222.  
  223. 這邊是2D/1D凸性優化的核心代碼：\\
  224.  
  225. \begin{C++}
  226. for(int len = 2; len <= n; len++){  // 枚舉區間長度 (i - j)
  227.    for(int i = 1, r = len; r <= n; i++, r++){
  228.        // 枚舉長度為 len 的所有區間
  229.        dp[i][j] = INF;
  230.        for (int k = p[i][j-1]; k <= p[i+1][j]; k++)
  231.            if (dp[i][j] > dp[i][k] + dp[k+1][j] + w(i, j)){
  232.            // 更新 dp 陣列
  233.            dp[i][j] = dp[i][k] + dp[k+1][j] + w(i, j);
  234.            p[i][j] = k;  // 記錄（最小）轉移來源
  235.        }
  236.    }
  237. }
  238. \end{C++}
  239.  
  240. \subsection{2D/1D 凹性優化}
  241.  
  242. 凹性沒有好性質 QQ\\
  243.  
  244. 所以只能枚舉$i$，讓dp狀態變成一維，用$N$次的1D/1D解決了。時間複雜度$N^2\log n$。
  245.  
  246. \subsection{習題}
  247.  
  248. 待補 QQ
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!