一、四邊形不等式
感覺四邊形不等式用的時候是:利用第j-1層的dp[i][j-1]和dp[i+1][j-1]兩個值的轉移位置s[i][j-1],s[i+1][j-1]來限制 k 的枚舉範圍……進而降低時間複雜度。
目前我做過的可以用四邊形不等式的題都是區間DP的……如果有路過的神牛做過别的類型的請在評論區留言,萬分感謝。
學習: 趙爽論文《動态規劃加速原理之四邊形不等式》
這一段的題目是看了下 shiwei408的總結
題目:(個人感覺難度從低到高)
1.石子合并(NOIP難度的石子合并就不用我找了吧……相信大家都寫過$n \leq 100$的)
二、單調隊列優化
UPD:2015-03-10 23:00:30
單調隊列優化一般可以用來優化動規方程類似$f[i]=max/min(f[k])+g[i] $的DP。
那麼應用的時候一般主要要考慮兩個東西:
1.将與$i$相關的部分分離出來,全部塞到$g[i]$這一項中,剩下的就是我們可以維護單調性的東西!(參考股票交易等題)
2.轉移範圍,即$k$的取值範圍!這也是所有動态規劃中都很重要的一點……這裡我們需要考慮隊列中時刻維護着【目前階段$i$的合法決策隊列】,是以我們需要考慮每個元素進隊的時機!以及隊首元素出隊的時機!避免某個目前無法轉移的決策過早地将其他合法決策從隊列中彈出來(由于單調性)(參見劃區灌溉/Fence兩題)
題目:(這次就直接粘題解了……)
1.滑動視窗
2.【HDOJ】【3415】Max Sum of Max-K-sub-sequence
3.【HDOJ】【3530】Subsequence
4.【BZOJ】【1855】【SCOI2010】/【HDOJ】【3401】股票交易
5.【BZOJ】【1986】【USACO 2004 Dec】/【POJ】【2373】劃區灌溉
6.【POJ】【1821】Fence
7.【BZOJ】【2500】幸福的道路
三、斜率優化
終于搞明白這個神奇的東西了……當初真是被這個和四邊形愁死了……
(UPD:2015-06-08 18:00:17 然而這個并不是完整的斜率優化sad)
首先明确我們要做的事情:利用決策的單調性,減少決策數
然後去看看論文吧……(其實感覺我把要寫的東西都寫在第一題的題解裡了……)
1.【BZOJ】【1096】【ZJOI2007】倉庫建設
2.【BZOJ】【1597】【USACO 2008 Mar】土地購買
3.【BZOJ】【1911】【APIO2010】特别行動隊commando
4.【BZOJ】【1010】【HNOI2008】玩具裝箱Toy