<style> .reveal .slides { text-align: left; } </style> # DP optimization Competitive programming 2 2021/10/25 ---- * 滾動 * 二進位分解 * 矩陣快速冪 * 單調隊列 * 狀態壓縮 --- ## 滾動DP 給兩個字串，求其中的最長共同子序列 (Longest Common Subsequence) x = 'cabdefga' y = 'dcea' LCS(x,y) = 3 ('dea', 'cea') ---- 先列出 dp 轉移式 dp[i][j] = max(dp[i-1][j],dp[i][j-1]); if x[i] != y[j] dp[i-1][j-1] + 1 if x[i] == y[j] 儲存狀態 如果 |x| 為 n, |y| 為 m 則需要開 dp[n][m] 的陣列 ---- ### 滾動優化 - 空間優化 <div style="font-size: 30px"> 可以注意到當我們在求 dp[i][j] 時 只需要用到 dp[ i-1 ][ j ], dp[ i ][ j-1 ], dp[ i-1 ][ j-1 ] 不需要用到 dp[i-2][k], dp[i-3][k], dp[i-4][k], ... (k $\in$ 1~m ) 所以我們只需要開 dp[2][m] 的大小 </div> dp[i&1][j] = max(dp[~i&1][j],dp[i&1][j-1]); if x[i] != y[j] dp[~i&1][j-1] + 1 if x[i] == y[j] 最後答案會存在 dp[n&1][m] &1 為取二進位最後一個位元是 0 或 1 ~ 是取補數，每個位元 0 變 1，1 變 0 ---- <div style="font-size: 30px"> 滾動不僅降低空間複雜度， 執行時間也會因為空間大小而有所差別 部分題目可能會因為沒有滾動造成常數過大而TLE 以下為例題有無滾動的差別 [b953: 能力越大責任越大](https://zerojudge.tw/ShowProblem?problemid=b953) </div>  --- ## 有限背包問題 <div style="font-size: 30px"> 有一個容量為 $W$ 的背包，及 $N$ 種物品，每種物品有各自的重量 $w_i$ 和價值 $v_i$，且每種物品數量有 $k_i$ 個，求在重量不超過 $W$ 的情況下，背包能塞的最大價值是多少 </div> W = 10 N = 3 item1 : w_i = 3, v_i = 5, k_i = 3 item2 : w_i = 2, v_i = 2, k_i = 5 item3 : w_i = 4, v_i = 6, k_i = 1 <div style="font-size: 30px"> 最佳拿法 item1 拿2個, item3 拿1個, 價值為 16 </div> ---- ### 作法 <div style="font-size: 30px"> 將每種物品取不同個視為不同東西 </div> item1 : w_i = 3, v_i = 5, k_i = 3 <div style="font-size: 30px"> 以 item1 有三個為例，則視為 3 個不同物品 </div> w_i = 3, v_i = 5 w_i = 6, v_i = 10 w_i = 9, v_i = 15 <div style="font-size: 30px"> 分別去做背包 每個獨立物品做背包複雜度 $O(W)$ 現在有 $N$ 種物品且每種有 $K$ 個 複雜度為 $O(NWK)$ </div> ---- ### 二進制分解 <div style="font-size: 30px"> 其實每種物品有 $K$ 個，不需要K種組合(1~K)都做一次 我們只需要做 $\lfloor lgK \rfloor$ 次就好 分別捆成 1個、2個、4個、8個、16個、...、$2^{\lfloor lgK \rfloor}$ 這些捆的組合，就可以湊出數量1~k的所有物品 以數量為9為例 分別做1 2 4 8則 </div> 1=1 2=2 3=1+2 4=4 5=4+1 6=4+2 7=4+2+1 8=8 9=8+1 ---- ### 複雜度 <div style="font-size: 35px"> $O(NWK)$ 降成 $O(NWlgK)$ </div> --- ## 矩陣快速冪 <div style="font-size: 25px"> 先備知識 : 快速冪 </div> #### 問題 <div style="font-size: 35px"> 求出費波那契數的第 $k (0 \le k \le 10^{18})$ 項 % 1000000007 直接 $O(N)$ 做 $\to$ TLE </div> ---- #### 轉移式 f[n] = f[n-1] + f[n-2] #### 列成矩陣 $\begin{bmatrix} f[n]\\f[n-1] \end{bmatrix}\quad = \begin{bmatrix} 1&1\\1&0 \end{bmatrix}\quad \times \begin{bmatrix} f[n-1]\\f[n-2] \end{bmatrix}\quad$ ---- ### 求出第N項 一開始我們有第0項和第1項 要求出第 $N$ 項的話 $\begin{bmatrix} f[n]\\f[n-1] \end{bmatrix}\quad = {\begin{bmatrix} 1&1\\1&0 \end{bmatrix}\quad}^{N-1} \times \begin{bmatrix} f[1]\\f[0] \end{bmatrix}\quad$ ---- ### 複雜度 要算出 ${\begin{bmatrix} 1&1\\1&0 \end{bmatrix}\quad}^{N-1}$ 用快速冪優化 $O(lgN)$ 矩陣乘法為 $k^3$ ( $k$ 為矩陣大小) 因此總複雜度為 $O(k^3lgN)$ ---- ### 程式碼 多載矩陣乘法 ```cpp= #define MOD 1'000'000'007 #define ll long long vector<vector<ll>> operator*(const vector<vector<ll>>& lhs,const vector<vector<ll>>& rhs){ vector<vector<ll>> ret(lhs.size(),vector<ll>(rhs[0].size(),0)); for(int i=0;i<lhs.size();i++){ for(int j=0;j<rhs[0].size();j++){ for(int k=0;k<rhs.size();k++){ ret[i][j] += lhs[i][k] * rhs[k][j] % MOD; ret[i][j] %= MOD; } } } return ret; } ``` ---- ### 程式碼 矩陣快速冪 ```cpp= vector<vector<ll>> init_value={{1},{0}}; //第0,1項 vector<vector<ll>> base={{1,1},{1,0}}; //費式數列轉移式 vector<vector<ll>> matrix={{1,0},{0,1}}; //單位矩陣 // x^y while(y){ if(y&1){ matrix = matrix * base; } base = base * base; y >>= 1; } matrix = matrix * init_value; cout<< matrix[0][0] << endl; ``` --- ### 單調隊列優化 例題 [相隔小於一定距離最小總和子序列](https://zerojudge.tw/ShowProblem?problemid=c528) ---- ### 轉移式 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$ 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]); } } ``` <div style="font-size: 30px"> 看上面程式碼會發現 3~5行求的就是區間 [i-k,i-1] 之間的最小值 因此可以用線段樹優化，找區間最小值 </div> ```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) ---- ### 單調隊列 但還可以做得更好，會發現我們在求第i項的dp值時 只需要保留[i-k,i-1]的值就好，更前面的完全用不到 並且如果有一個算出來的值比前面的都好，那前面的值都不需保留 因為已經有一個更好的了 ---- ### deque STL 資料結構，每次可以 $O(1)$ 從頭尾新增刪除元素 因此 我們每次算出一個dp值就看說 deque 裡面的比他小的元素都刪掉，只需保留比他大的就好 並且如果裡面有值過期(index < i-k)，則也將他刪除 deque裡面的元素最後只會單調遞增 ---- ### 例子 9 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個點m條邊 保證連通，邊上有權重 一開始有一個商人在節點0的位置， 他希望走過所有的點(0~n-1每個點)， 並且最後回到節點0 </div> ---- <div style="font-size: 30px"> 會發現如果每個點對之間都有連邊 那直接暴力dfs複雜度會變成 $O(N!)$ 而如果 dp 的話記錄說哪幾個點有走過， 總狀態數為 $2^n$ (每個點有走過或沒走過) 並且從當下狀態轉移到下一個狀態複雜度為 $O(N)$， 選擇下一個點要走到哪 </div> ---- <div style="font-size: 30px"> 而對於每個點是否走過，我們可以用一個數字來記錄儲存狀態 假設5個點，第0,1,4個點有走過,第2,3還沒走過 則可以表示成 10011 從左至右分別為第4、第3...第0個點是否走過 然後存成十進位 19(10011) 而全部都有走過的狀態為 11111 反過來為 00000 因此我們開的大小為 dp[n][1<<n] n為當前狀態最後一個點走到的點是誰，以及目前走過哪些點 </div> ---- 而要判斷當下狀態status的某個點x是否走過 ```cpp= flag = status >> x & 1; // status右移x格去 and 1 如果為1代表走過 ``` 轉移狀態，將當前狀態status多加一個點x ```cpp= next_status = status | (1 << x) ; // 原本狀態跟第x個點的位置去 or // 記得位元運算都盡量括號，避免優先度太低造成bug ``` ---- 複雜度 $O(2^nn^2)$ ```cpp= int dp[n][1<<n]; int dis[n][n]; //可以先用floyd-warshall跑過全點對最短路徑 memset(dp,0x3f3f3f3f,sizeof(dp)); for(int status=0;status<(1<<n);status++){ //窮舉每一種狀態 for(int j=0;j<n;j++){ //前一個點 if(~status>>j&1) continue; for(int k=0;k<n;k++){ //下一個點 if(status>>k&1) continue; dp[k][status|(1<<k)] = min(dp[k][status|(1<<k)],dp[j][status] + dis[j][k]); } } } } ``` --- ### Question Time and Practice [Homework Link](https://vjudge.net/contest/464705) <div style="font-size: 30px"> 提交期限兩星期，下下星期一 18:30 截止 </div>