在這之前我花了很多時間讀四邊形優化，然後都看不懂QQ。直到今天我才真正看懂1D/1D凹性以及1D/1D凸性優化。我認為四邊形優化真的很難，我在網路上有看到很多關於四邊形優化的說明，像是建中講義以及吳仲昇的chino，但是在下才疏學淺、數學不好、不懂繁雜的符號，最後看到了2014資訊之芽的講義才完全理解。因此在此我要說明一下我對於四邊形優化的理解，希望能幫到普羅大眾，至於嚴謹的說明以及證明我就不解釋了，這部分可以參閱吳仲昇的chino，直接google "四邊形優化" 第一個應該就是他吧。
1D/1D的優化簡單來說：
就是有一個二維的DP表格，這個表格符合某種單調性（以下會解釋）。
而我們想要求的是，整個表格的極值。
這是一個DP表格
(左下角的狀態不存在 所以圖中把它省略了)
在這個表格中，所有的狀態都可以在前面的狀態已經做好的情況下O(1)求得，所以很當然的有O(N^2)的作法。
一般做法是一次做一行(在此直排稱為行)，每行先各自找出最優解，然後再比較每行的最優解即可。
而「優化」也是一行一行做，每當有一個列能夠插入時，就將之插入，並維護當前最優解，這種東西的複雜度可以均攤到O(1)+O(lgN)=O(lgN) 所以總共是O(NlgN)。
以下將說的更詳細一點。
首先，我們要知道甚麼是單調性，
在此不贅述四邊形不等式(可以參閱吳仲昇的chino)
簡而言之，單調性在這裡的呈現就是
每行最優解的位置會遞增(或遞減)(圖片右上角)
利用這個特性，我們就可以做出這樣的算法：
下列步驟執行n次(假設有n列)
1.插入新的一列
2.維護每一行的＂目前＂最優解
舉個例子好了
就是做好第一＂列＂的時候的樣子。
你可能會表示：
我只看到一列而已啊！
是的，這表示 當前的最優解的列範圍，只有包含第一列。
第二張圖：
我們要執行第二次了
所以我們來插入第二列
第三張圖：
是第二列插入完成的時候的樣子
而當前的最優解的列範圍，有包含第一列還有剛剛插入的第二列，總共兩列，也就是說當前每行的最優解不是在第一列就是在第二列。
因此以上的＂目前＂就是指，當下已經有存在的列。
那麼是說 在做同一行時，有沒有可能一次要插入多列、或不用插入？
這是有可能的。
像是以下的表格，只要它符合四邊形不等式的性質，也適用四邊形優化。
因此表格的形狀是無關緊要的，並不是說每做一行 就要插入一列。
接下來終於要說實作的部分了
首先要說明
存區間的容器是deque
存區間的方法是存左右界
看看同一張圖
很明顯的
我們正在做第i列
由於解答會有往右上的趨勢
所以說
可能變以下左圖，也可能變以下右圖。
所以我們的步驟是
1.看看能不能把C全部都殺掉
方法就是跟C的最後一行那格比比看
要是可以 ，就代表贏了整個C（就像右上那張圖）
就可以一次pop掉整個C
然後繼續對B做一樣的事
直到最後贏不了
2.贏不了之後
代表兩列最優解的斷層
就在最後沒有被pop掉的區間內
所以可以對這個區間做二分搜
然後就可以把原本的區間的左界改一下
然後再push新的最優解列即可
在這兩個步驟中
步驟1均攤是O(1)
因為每次都push一個區間而已
所以總共最多pop n個
步驟2則是二分搜
即為O(lgn)
所以總共O(NlgN)
------------------------------------------------------------------------------
最後
我們回到題目
它的狀態是
以i作為頂邊
以j作為底邊
的面積
面積很好求
左右界的交集*上下界的差距就是了( O(1) )
所以原本是O(n^2)
然後我們會發現它的單調性
枚舉底邊
使用的頂邊具有單調性(就是只會一直往右下使用 不會往回)
變成O(NlgN)
補充一些實作上的細節
由於我們主要是想要求每行的最大值
所以在插入列時
就是以行為主體
看看能插到哪列
就一次插完
所以實作上就會變得像是枚舉行
因此每次做完一些列
就可以得到該行的最大值
以下是我的AC code作為參考。
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef long long ll; | |
| int n, m; | |
| ll tl[100010], th[100010], bh[100010], bl[100010], ans; | |
| inline ll cnt(ll a,ll b){ | |
| return max( (tl[b] - bl[a-1]) * (bh[a] - th[b]) , 0LL); | |
| } | |
| struct qd{ | |
| int l, r, h; | |
| }; | |
| int main(){ | |
| ios_base::sync_with_stdio(0); cin.tie(0); | |
| cin >> n; | |
| n >>= 1; | |
| for(int i = 1; i <= n; ++i) | |
| cin >> tl[i] >> th[i + 1]; | |
| for(int i = 2; i <= n; ++i){ | |
| tl[i] += tl[i - 1]; | |
| th[i + 1] += th[i]; | |
| } | |
| cin >> m; | |
| m >>= 1; | |
| for(int i = 1; i <= m; ++i) | |
| cin >> bh[i] >> bl[i]; | |
| for(int i = 2; i <= m; ++i){ | |
| bh[i] += bh[i - 1]; | |
| bl[i] += bl[i - 1]; | |
| } | |
| deque<qd> sk; | |
| sk.push_back({1, m, 1}); | |
| int p = 2; | |
| for(int i = 1; i <= m; ++i){ | |
| if(sk.front().r < i) | |
| sk.pop_front(); | |
| sk.front().l = max(sk.front().l, i); | |
| while(p <= n && bh[i] > th[p]){ | |
| while( sk.size() && cnt(sk.back().l, sk.back().h) < cnt(sk.back().l, p) ) | |
| sk.pop_back(); | |
| if(sk.empty()) | |
| sk.push_back({i, m, p}); | |
| else{ | |
| int hi = sk.back().r + 1; | |
| int de = sk.back().l; | |
| while(de < hi - 1){ | |
| int mid = de + hi >> 1; | |
| if(cnt(mid, p) > cnt(mid, sk.back().h)) | |
| hi = mid; | |
| else | |
| de = mid; | |
| } | |
| sk.back().r = de; | |
| if(hi <= m) sk.push_back({hi, m, p}); | |
| } | |
| ++p; | |
| } | |
| ans = max(ans, cnt(i, sk.front().h)); | |
| } | |
| cout << ans << '\n'; | |
| } |
