<style> .reveal .slides { text-align: left; font-size:30px } </style> # DP optimization Introduction to Competitive Programming 2022/05/25 ---- - DP with Data Structure - 單調隊列優化 - 最大子矩陣 - nearest greater element --- ## DP with Data Structure Longest Increasing Subsequence 給你一個長度為 $N$ $(1 \le N \le 10^5)$ 的整數序列 $a$， 求出最長的子序列其元素為非嚴格遞增 ---- ## DP 轉移式 `dp[i]` 為以第 $i$ 個元素為結尾的最佳解 轉移由前面某個元素 `a[j]` 為結尾且 `a[j]` $\le$ `a[i]` `dp[i] = max(dp[j]) + 1` ; \( `j < i` $\land$ `a[j]` $\le$ `a[i]`) 複雜度 $O(N^2)$ ---- `dp[i] = max(dp[j]) + 1` ; \( `j < i` $\land$ `a[j]` $\le$ `a[i]`) 要求以上轉移式，等價於求所有 $\le$ `a[i]` 的元素中，最大的 dp 值 可以用線段樹維護，線段樹儲存的為所有出現過的值 以序列 [1, 3, 2, 4, 3] 為例 可以算出分別的 dp 值為 [1, 2, 2, 3, 3]  最底層的元素為到目前為止 分別以數字 1, 2, 3, 4 為結尾的元素中最大的 DP 值 ---- 計算 DP 從第一個元素開始，一開始線段樹每個值都設為 0 每次算 DP[i] 等於前面所有小於自己的元素中最大的 DP 值 直接 query 線段樹小於等於自己的區間的最大值即可 ```cpp dp[i] = segTree.query(0, lower_bound(ind.begin(),ind.end(),a[i]))-ind.begin()) + 1; ``` 原本需要迴圈跑過全部小於自己的所有元素 DP 值， 現在只需要區間詢問最大值+1 即為 dp[i] 複雜度 $O(NlgN)$ ---- ### 單調隊列優化 例題 [相隔小於一定距離最小總和子序列](https://zerojudge.tw/ShowProblem?problemid=c528) 給定一個長度為 $N$ 的整數序列及一個正整數 $K$， 請蓋掉任意個數字使得原序列中任意的連續 $K$ 個數字都至少有一個數字被蓋掉了，請問蓋掉的數字的總和最小為多少？ ---- 給定一個長度為 $N$ 的整數序列及一個正整數 $K$， 請蓋掉任意個數字使得原序列中任意的連續 $K$ 個數字都至少有一個數字被蓋掉了，請問蓋掉的數字的總和最小為多少？ ### 轉移式 `dp[i]` 定義為 以第 `i` 個結尾，並且蓋掉第 `i` 個元素的最佳解 `dp[i] = min(arr[i] + dp[j]) ，i-k` $\le$ `j` $<$ `i` ---- 注意題目 $N, K$ 大小 $K \le N \le 10^6$ 直接做 $\to 10^{12}$ TLE ```cpp= for(int i=0;i<n;i++){ //TLE dp[i] = (i<k?arr[i]:INF); for(int j=i-1;j>=max(i-k,0);j--){ dp[i] = min(dp[i],dp[j] + arr[i]); } } ``` ---- ### 優化? ```cpp= for(int i=0;i<n;i++){ //TLE dp[i] = (i<k?arr[i]:INF); for(int j=i-1;j>=max(i-k,0);j--){ dp[i] = min(dp[i],dp[j] + arr[i]); } } ``` 看上面程式碼會發現 3~5行求的就是區間 [i-k,i-1] 之間的最小值 因此可以用線段樹優化，找區間最小值 ```cpp= for(int i=0;i<n;i++){ mn = (i<k?arr[i]:INF); mn = min(mn,segTree.query(max(i-k,0),i-1)); segTree.update(i,mn); } ``` 複雜度 $O(NlgN)$ ---- 而線段樹實作複雜度很高， 實際上可以用 STL priority_queue 儲存 每次放進去 pair(dp[i], i); 每次取 priority_queue 最小的 dp 值， 而如果最小值過期則直接 pop 掉 --- ### 單調隊列 會發現我們在求第 $i$ 項的dp值時 只需要保留 $[i-k,i-1]$ 的 dp 值就好，更前面的完全用不到 並且對於所有(i, j) 如果 dp[i] $\ge$ dp[j] $\land$ i < j 只需要保留 dp[j] 即可， dp[i] 不可能更新最小值 所以最後剩下的 DP 值都會符合 如果 i < j 則 dp[i] < dp[j] 而可以用 deque 儲存這些元素 ---- ### deque STL 資料結構，每次可以 $O(1)$ 從 front, end 新增刪除元素 因此 每次算出第 i 項的 dp 值放進 deque 前 裡面的比 dp[i] 大的值都可以 pop 掉，只需保留比他小的 dp 值就好 並且如果裡面有值過期(index < i-k)，則也將他刪除 deque 裡面的元素最後只會單調遞增 $dp[i]<dp[j] \ \forall \ i<j$ ---- ### 例子 n = 9, k = 3 8 3 6 5 7 -5 1 8 5 ---- ### 範例 ```cpp= deque<pair<int,int>> dq; //index, value int calc(){} for(int i=0;i<n;i++){ // dp 求最大值 while(!dq.empty() && dq.front().first < i-k) dq.pop_front(); //判斷dq裡的東西有沒有過期 dp[i] = calc(); while(!dq.empty() && dq.back().second >= dp[i]) dq.pop_back(); //判斷dq裡的東西是不是比當前dp[i]小，如果比較小就去掉 dq.push_back(make_pair(i,dp[i])); } //保證dq從左至右value由大到小 ``` ---- ### 複雜度 $O(N)$ --- ## 最大矩形面積 <div style="font-size: 30px"> 題目給你 $N \times M ( N, M \le 2000)$ 的矩陣，上面有一些格子有障礙物， 要找出一個子矩陣，沒有任何障礙物。 問你所有合法的子矩陣中，最大面積為多少?  以上圖為例，假設黑色為障礙物，則合法中最大的子矩陣為紅色框起來的，面積為6 </div> ---- ## 想法1 <div style="font-size: 30px"> 暴力窮舉所有矩陣判斷合不合法 $O(N^6)$ * 窮舉左上角 $O(N^2)$ * 窮舉右下角 $O(N^2)$ * 窮舉矩陣內的每一格判斷是否有障礙物 $O(N^2)$ </div> ---- ## 想法2 <div style="font-size: 30px"> * 窮舉左上角 $O(N^2)$ * 窮舉右下角 $O(N^2)$ * ~~窮舉矩陣內的每一格判斷是否有障礙物 $O(N^2)$~~ 計算前綴和，左上到每個點為右下的矩形裡面的障礙物數量  如果要計算區間內的障礙物數量，用排容原理 假設要求 [2,2] 到 [3,4] 子矩陣的障礙物數量 則為 prefix[3][4] - prefix[3][1] - prefix[1][4] + prefix[1][1] </div> ---- * 窮舉左上角 $O(N^2)$ * 窮舉右下角 $O(N^2)$ 複雜度 $O(N^4)$ 此作法複雜度足夠快去解昨天 [CPE 第五題](https://onlinejudge.org/external/1/108.pdf) ---- ## 想法3 ### DP 先 $O(N^2)$ 計算出每格往上最高可以到多高  之後窮舉以每格為右下角的所有可能矩形 每次往左判斷從起始格到當前往上最高可以多高 以 [3,4] 為例 往左 1 格高度最高可以為 2 往左 2 格高度最高可以為 2 往左 3 格高度最高可以為 1 ---- * 窮舉右下角 $O(N^2)$ * 窮舉左界 $O(N)$ 複雜度 $O(N^3)$ 但...還不夠 $N^3 = 8 \cdot 10^9 \to TLE$ ---- ## O($N^2$) 做法 先 DP 每格往上有幾格可以用 一樣窮舉以每個點當右下 對於每一個 row 變成轉換為以下問題 [ZJ c907](https://zerojudge.tw/ShowProblem?problemid=c907) 現有 N 個寬度為1單位的長條圖(例如下圖所示)，試求此長條圖中可以形成的最大矩形面積。  ---- ## 作法 使用 stack 維護遞增子序列 stack 裡儲存:從 index $i$ 開始，可以放的最高高度為 $h$ [2, 5, 7, 4, 5]  前三個長度為遞增的，因此可以直接放進 stack 裡面 stack: [(1, 2), (2, 5), (3, 7)] ----  到前 3 個為止 stack 裡的都是合法的 從 index 1 開始到目前第 3 個為止可以放的矩形最高高度為 2 從 index 2 開始到目前第 3 個為止可以放的矩形最高高度為 5 從 index 3 開始到目前第 3 個為止可以放的矩形最高高度為 7 而第 4 個高度為 4，如果直接放進去 stack 會破壞維護的性質 因此所有高度比他高的都要 pop 掉 而 pop 掉的時候順便更新答案 ---- ## pop 更新答案  stack: [(1, 2), (2, 5), (3, 7)] 當前為 (4, 4) 因此要 pop 掉 (2, 5), (3, 7) 也就是 index 2 開始高度 5 只能到 index 3 index 3 開始高度 7 只能到 index 3 分別用以上兩種高度 $\times$ 寬度更新答案(最大面積) (3-2+1)*5, (3-3+1)*7 ----  更新完後即可把當前高度放進 stack 裡面 原本要放進去為 (4, 4) 從 index 4 開始到目前為止可以放的矩形最高高度為 4 但會發現 pop 掉的位置高度都 $\ge$ 當前高度 因此放進去的為 pop 掉的所有位置最前面那個 為 (2, 4) 從 index 2 開始到目前為止可以放的矩形最高高度為 4 ----  做完後 stack 裡會有 [(1, 2), (2, 4), (5,5)] 為遞增子序列分別為從 從 index 1 開始到最後可以放的矩形最高高度為 2 從 index 2 開始到最後可以放的矩形最高高度為 4 從 index 5 開始到最後可以放的矩形最高高度為 5 而也可以用這些去更新答案(最大面積) (5-1+1)*2, (5-2+1)*2, (5-5+1)*5 ---- ## 複雜度 從左往右掃描過去 每個高度會被放到 stack 一次，最多也只會 pop 出來一次 複雜度為 $O(M)$ 而如果是要求最大子矩形的面積總共有 N 行 每行做一次複雜度為 $O(NM)$ --- ## nearest greater element 給你一個長度為 $N$ $(1 \le N \le 10^6)$ 的正整數序列 $a$ 對於每個數字，求出往左跟往右第一個大於他的數字， 如果找不到就輸出 -1 sample input ``` 5 4 2 1 7 3 ``` sample output ``` -1 7 4 7 2 7 -1 -1 7 -1 ``` ---- 暴力可以 O($N^2$) 每個數字往左或往右找 或者維護一顆 取max的線段樹從當前位置找下去， 遞迴時 greedy 選盡量靠近的位置 複雜度 O(NlgN) ---- 用 stack 做 類似求最大子矩陣作法 往左跟往右各做一次 分別維護一個遞減序列 從第一個元素開始 push 進去 如果 stack 的 top $\le$ 當前元素則 pop 掉 直到 stack 變空的或 top 比當前元素大為止 ---- a = [4, 2, 1, 7, 3] 第 1 個元素: stack 是空的左邊沒有比他大的值 接著放進 stack 裡, stack = [4] 第 2 個元素: stack 的 top 為 4 比當前元素大, 紀錄答案並放進 stack 裡, stack = [4, 2] 第 3 個元素: stack 的 top 為 2 比當前元素大, 紀錄答案並放進 stack 裡, stack = [4, 2, 1] 第 4 個元素: stack 的 top 為 1, 比當前元素小 pop 到空或者當前元素大為止 接著放進 stack 裡, stack = [7] 第五個元素: stack 的 top 為 7, 比當前元素大, 紀錄答案並放進 stack 裡 ---- 複雜度 $O(N)$ --- ### Question Time and Practice [Homework Link](https://vjudge.net/contest/497108) 提交期限到下星期三 6/1 23:59 截止