owned this note
owned this note
Published
Linked with GitHub
---
tags: Training
type: slide
---
<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 截止
Google Drive
Gist
Clipboard
Sign in with Wallet
