0. 前言
寫完這篇文章后發現自己對于 DP 的優化一竅不通，所以補了補 DP 的一些優化，寫篇 blog 總結一下，
1. 單調佇列/單調堆疊優化
1.2 演算法介紹
這應該算是最基礎的 DP 優化方法了，
顧名思義，單調佇列/單調堆疊優化 DP 就是保持容器內元素的單調性，以達成減少冗余狀態的目的，
舉單調佇列的例子來說，當一個元素的兩種屬性（例如下標和權值）都優于另一元素時，就可以用此元素更換掉另一元素，這也正是 OI 界流傳說法“當一個人比你小且比你強時，你就被彈出單調佇列了”的原理，
我們以下面的例題作為例子來更具體地闡述這個演算法，
1.3 適用范圍&區別
一般來說，形如 \(f(i)=\max(f(j)+F(i)+F(j))\) 的式子都可以考慮適用單調佇列/單調堆疊進行優化，（其中 \(F(i)\) 和 \(F(j)\) 表示和 \(i,j\) 有關的函式）
應該大部分人剛學這兩種東西的時候都有一種疑惑：啥時候用單調佇列，啥時候用單調堆疊呢？（至少我有
其實，它們兩的本質區別還是其結構上的區別，單調堆疊通常用新加進來的東西替換掉一些堆疊頂元素，而單調佇列是可能兩端同時修改的，
在一下例題中我也會著重分析兩者的使用，
1.4 例題
I. P1886 滑動視窗
題目鏈接
這個不是優化 DP，就是最經典的裸的不能再裸的單調佇列，
大力單調佇列即可，時間復雜度 \(O(n)\)，
II. CF372C Watching Fireworks is Fun
題目鏈接
OI Wili 推薦的題
題目大意：一個數軸上有 \(n\) 個點，每個點在位置 \(a_i\)，有 \(m\) 個煙花要放，開始時間 \(t_i\)，你一開始的位置隨便，每一單位時間可以最多走 \(d\) 這么多的距離，在 \(x\) 看到第 \(i\) 個煙花的快樂值為 \(b_i-|a_i-x|\)，求最大的總代價，
資料范圍：\(n\leq 150000,m\leq 300\)，
看到這個資料范圍就知道大概是 \(O(nm)\) 的演算法（最多要卡卡常），
我們容易設計出 DP 狀態 \(f(i,j)\) 表示放第 \(i\) 個煙花，位置在 \(j\) 時的最大快樂值，
轉移：\(f(i,j)=\max_{j-(t_i-t_{i-1})\cdot d_i\leq k\leq j+(t_i-t_{i-1})\cdot d_i}(f(i-1,k)+b_i-|a_i-j|)\)，
接下來就需要對 DP 進行優化了，首先因為當 \(i\) 和 \(j\) 確定時 \(b_i-|a_i-j|\) 可以看做常數，剩下的就可以用單調佇列去維護了，
注：本題使用單調佇列的原因為 \(k\) 兩邊都有限制，需要頭尾都更新，
時間復雜度 \(O(nm)\)，
代碼
III. P3572 [POI2014]PTA-Little Bird
題目鏈接
IV. P1973 [NOI2011] NOI 嘉年華
題目鏈接
V. P2254 [NOI2005] 瑰麗華爾茲
題目鏈接
2. 斜率優化
斜率優化自己學過好幾遍，也聽 dalao 講過，但是總是感覺半懂不懂的，這次索性把它給搞徹底了罷……
2. 1 演算法介紹
以 OI Wiki 上的例題為例，
題目大意：有 \(n\) 個玩具，每個玩具有一個價值 \(c_i\)，你需要將這 \(n\) 個玩具分成若干段，設一段 \([l,r]\) 的代價為 \((r-l+\sum_{i=l}^rc_i-L)^2\)，其中 \(L\) 為常數，求最小的總代價，
資料范圍：\(n\leq 5\times 10^4\)
使用 DP 優化的一般思路：先設計出一個超時的 DP 再優化，
設 \(f_i\) 表示前 \(i\) 個玩具的代價，那么得出轉移方程為：
\[f_i=\min_{j=0}^{i-1}\{f_j+(i-j-1+\sum_{k=j+1}^ic_k+L)^2\} \]用前綴和表示后即為：
\[f_i=\min_{j=0}^{i-1}\{f_j+(i-j-1+S_i-S_j+c_k+L)^2\} \]其中 \(S_i=\sum_{k=1}^ic_k\)，
這就是樸素的 \(O(n^2)\) 的 DP，
下面就要優化了，不過有個問題：DP 跟斜率有什么關系呢？
考慮將 DP 轉移方程轉化為決議幾何中直線的斜截式方程 \(y=kx+b\) 的形式，
我們先將只和 \(i,j\) 有關的歸為一類，常數歸為一類：\(a_i=s_i+i,b_i=s_i+i+L+1\)，然后原式可以寫成：
\[f_i=\min_{j=0}^{i-1}\{f_j+(a_i-a_j)^2\} \]然后可以令 \(y=f_j+b_j^2,k=2a_i,x=b_j\)，(P.S. 這個應該只要滿足 \(y=kx+b\) 都可以？)
此時需要最小化直線的截距，先將這些 \((x,y)\) 表示在平面直角坐標系中：
可以看到藍線連成了一個下凸殼，第一個紅線碰到的點使截距最小，
下面的問題就是怎樣維護這個凸包，發現存在斜率遞增，所以可以用單調佇列來維護，
代碼
2.2 例題
I. P4072 [SDOI2016]征途
題目鏈接
998244352. 參考資料
第 1 章：
- OI Wiki
第 2 章：
-
OI Wiki
-
洛谷玩具裝箱題解
本文來自博客園，作者：Jerry_Jiang，轉載請注明原文鏈接：https://www.cnblogs.com/Jerry-Jiang/p/16565671.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/501332.html
標籤：其他