--- tags: 自主學習 --- # 自主學習-演算法學習(每周進度與成果) 高二34623趙炫翔 # 本計畫所編的全部學習筆記 - [線段樹](/9WMgzFs6RbCZ3LQ5NSf7QQ) - [BIT](/fH6_FqTnQb2BHEV6EhG3lQ) - [模運算](/564I9dxSTf6crJP95qRnlQ) - [模反元素/模逆元](/zlqbqmRxTiqprniwOmkH6Q) - [快速冪&矩陣乘法&矩陣快速冪](/f6LDVf4yTNy-b4vf7kbx9g) - [LIS&LCS](/96ZnugpZRxqkW7LARlrWhg) - [背包問題](/HWN_qcwZTum7G-qiWgV7DA) - [單調隊列](/_VjchRMtRSyTgMyBQmB8QA) - [DP優化](/dvHGezXpRu-SLAj7McPc4A) # 第一周-線段樹 ## 本周成果 1. 複習線段樹的基礎概念，並強化實作熟悉度 2. 在DanDanJudge，用線段樹解出a710 ## 本周實作進度 ### a710筆記(9/2) [題目](http://203.64.191.163/ShowProblem?problemid=a710) 我的想法是用線段樹存0和1，0就是這個位置原本的數被刪掉了，1就是數還在 而從線段數第1項加到第k項，和就是舊數列第k項的數在新數列的位置 相反的新數列第t項在舊數列中的位置，就是從線段樹第1項開始加，當加到和t一樣時，這時線段樹的編號就是t在舊數列中的位置 而這個和具有單調性 所以可以利用二分搜找到新數列中的第k個在原本數列的位置 時間複雜度$O(Qlog^2N)/Q=2\times10^5,n=2\times10^5$ ### DDJ a710筆記補充(9/6) 我在看到解題列表後發現有很多人的解題時間都是0.1秒，看起來不像$O(Qlog^2N)$的解法，看起來像$O(QlogN)$，在學長提點和我的思考後，我發現先從線段樹取出值，然後再拿來二分搜根本沒必要，在線段樹內遞迴時就可以判段進入的子節點有沒有可能包含要查詢的值，就像在線段數內二分搜一樣。 --- $O(Qlog^2n)$ :::info :::spoiler <font color="00FF00">**AC**</font>_code ```cpp= #include<bits/stdc++.h> using namespace std; int n, q; vector<int> seg(800005); vector<int> arr(200005); #define m (l + r) >> 1 inline void build(int l = 0, int r = n, int i = 1){ if(r - l == 1){seg[i] = 1;return;} build(l, m, i << 1),build(m, r, i << 1 | 1); seg[i] = seg[i << 1] + seg[i << 1 | 1]; } inline int query(int ql, int qr, int l = 0, int r = n, int i = 1){ if(qr <= l || ql >= r){return 0;} if(ql <= l && qr >= r){return seg[i];} return query(ql, qr, l, m, i << 1) + query(ql, qr, m, r, i << 1 | 1); } inline void upt(int idx, int val, int l = 0, int r = n, int i = 1){ if(idx < l or idx >= r){return;} if(r - l == 1){seg[i] += val;return;} upt(idx, val, l, m, i << 1) , upt(idx, val, m, r, i << 1 | 1); seg[i] = seg[i << 1] + seg[i << 1 | 1]; } # undef m inline int bs(int x){ int l = 0,r = n,p = -1; for(int i = 0; i < 20; i++){ int m = (l + r) >> 1; if(query(0, m) == x) p = m - 1, r = m; else if(query(0, m) < x) l = m + 1; else r = m; } return p; } int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> q; for(int i = 0; i < n; i++) cin >> arr[i]; build(); int p = -1; while(q--){ int d ,k; cin >> d >> k; upt(bs(d),-1); cout << arr[bs(k)] << '\n'; } return 0; } ``` ::: ![](https://i.imgur.com/nNUCVIk.png) --- $O(Qlogn)$ :::info :::spoiler <font color="00FF00">**AC**</font>_code ```cpp= #include<bits/stdc++.h> using namespace std; int n, q; vector<int> arr(200005); vector<int> seg(800005); #define m (l + r) >> 1 void build(int l = 0, int r = n, int i = 1){ if(r - l == 1){seg[i] = 1;return;} build(l, m, i << 1), build(m, r, i << 1 | 1); seg[i] = seg[i << 1] + seg[i << 1 | 1]; } void upt(int idx, int l = 0, int r = n, int i = 1){ if(idx < l || idx >= r)return; if(r - l == 1){seg[i] = 0;return;} upt(idx, l, m, i << 1);upt(idx, m, r, i << 1 | 1); seg[i] = seg[i << 1] + seg[i << 1 | 1]; } int query(int val, int l = 0, int r = n, int i = 1){ if(val > seg[i] || val <= 0)return 1; if(r - l == 1 && val == seg[i])return l; return query(val, l, m, i << 1) * query(val - seg[i << 1], m, r, i << 1 | 1); } # undef m int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> q; for(int i = 0; i < n; i++){ cin >> arr[i]; } build(); while(q--){ int d ,k; cin >> d >> k; upt(query(d)); cout << arr[query(k)] << '\n'; } } ``` ::: ![](https://i.imgur.com/u6rgJtZ.png) --- # 第二周 ## 本周預期進度 1. 複習BIT的基礎概念，並強化實作熟悉度 2. 在DanDanJudge，用BIT解出a710 ## 本周成果 ### DDJ a710筆記 解題想法和上禮拜$O(Qlog^2N)$一樣 只是這次我把1加到k的工具換成了BIT 時間複雜度$O(Qlog^2N)$ --- $O(Qlog^2N)$ :::info :::spoiler AC_code ```cpp= #include<bits/stdc++.h> using namespace std; int n, q; vector<int> vc(200005); vector<int> bit(200005); int lowbit(int x) {return (x & -x);} inline void build(){ for(int x = 1; x <= n; x++){ int k = x; while(k <= n){ bit[k] ++; k += lowbit(k); } } } inline void upt(int x){ while(x <= n){ bit[x] --; x += lowbit(x); } } inline int query(int x){ while(x){ return query(x - lowbit(x)) + bit[x]; } return 0; } inline int BS(int idx){ int l = 1, r = n+1; int m = (l + r) >> 1; for(int i = 0; i < 20; i++){ int mval = query(m); if(mval > idx){ r = m; } else if(mval == idx){ if(mval - query(m - 1) == 0){ r = m; } } else if(mval < idx){ l = m + 1; } m = (l + r) >> 1; } return m; } int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> q; for(int i = 1; i <= n; i++){ cin >> vc[i]; } build(); while(q--){ int d , k; cin >> d >> k; upt(BS(d)); int i = BS(k); cout << vc[i] << '\n'; } } ``` ::: ![](https://i.imgur.com/O5t0rBw.png) --- # 第三周 ## 預計進度 BIT講義 線段樹講義 ## 講義 [線段樹](/9WMgzFs6RbCZ3LQ5NSf7QQ) [BIT](/fH6_FqTnQb2BHEV6EhG3lQ) # 第四周 ## 預計進度 學習快速冪 & 矩陣乘法 學習模運算和模逆元(不再計畫內，後來補的) 解DDJ a689 、TIOJ 2053、UVA 10870 ## 本周成果 ### DDJ a689筆記 [題目](http://203.64.191.163/ShowProblem?problemid=a689) 這題就是排列組合 只是這題的範圍非常大 所以需要一點模運算 我是先把1\~100000階乘和1\~100000階乘的模逆元都先存起來 然後計算字串重複的個數 然後再用域先處理好的階乘數乘上重複個數階乘的模逆元 (等同於除上重複個數階乘--->費馬小定理$a^{-1}≡1\ (mod\ p)\ p為質數$) --- :::info :::spoiler <font color="00FF00">**AC**</font>_code ```cpp= #include<bits/stdc++.h> using namespace std; #define int long long #define mod 1000000007 #define maxn 100005 int factorial_inv[maxn]; int factorial[maxn]; int q_pow(int a, int x){ int sum = 1; while(x > 0){ if(x & 1)sum = (sum %mod)* (a % mod); a = (a % mod) * (a % mod); x >>= 1; } return sum % mod; } void build(){//a^(p-2)≡a^(-1) (mod p) factorial[0] = 1; for(int i = 1; i < maxn; i++){ factorial[i] = (factorial[i - 1] * i)%mod; factorial_inv[i] = q_pow(factorial[i], mod-2); } } signed main(){ ios::sync_with_stdio(0);cin.tie(0); build(); int t; cin >> t; while(t--){ string s; cin >> s; vector<int> c(1000); for(auto& i : c)i = 0; for(int i = 0; i < s.size(); i++){ c[(int)s[i]]++; } vector<int> vc; for(int i = '0'; i <= '9'; i++ ){ if(c[i] > 1)vc.push_back(c[i]); } for(int i = 'A'; i <= 'z'; i++){ if(c[i] > 1)vc.push_back(c[i]); } int ans = factorial[s.size()] % mod; for(int i = 0; i < vc.size(); i++){ ans = ans *(factorial_inv[vc[i]] % mod); ans %= mod; } cout << ans << '\n'; } } ``` ::: ![](https://i.imgur.com/y4S1rAR.png) --- ### TIOJ 2053 筆記 [題目](https://tioj.ck.tp.edu.tw/problems/2053) 這題的遞迴式是$X_n = bX_{n-1} + aX_{n-2}$ 已知 $$ \left[ \begin{array}{1} X_n \\ X_{n-1} \end{array} \right]= \left[ \begin{array}{1} b & a \\ 1 & 0 \end{array} \right] \left[ \begin{array}{1} X_{n-1} \\ X_{n-2} \end{array} \right] $$ 可知 $$ \left[ \begin{array}{1} X_{n+1} \\ X_{n} \end{array} \right]= \left[ \begin{array}{1} b & a \\ 1 & 0 \end{array} \right]^{n} \left[ \begin{array}{1} X_1 \\ X_0 \end{array} \right] $$ 得出了這個式子 接下來就只要用矩陣快速冪答案就出來了 --- :::info :::spoiler <font color="00FF00">**AC**</font>_code TIOJ 2053 ```cpp= #include<bits/stdc++.h> using namespace std; #define mod 1000000007 #define int long long struct martix{ int m[2][2]; martix operator*(martix a){ martix r; for(int i = 0; i < 2; i++){ for(int j = 0; j < 2; j++){ r.m[i][j] = 0; } } for(int i = 0; i < 2; i++){ for(int j = 0; j < 2; j++){ for(int k = 0; k < 2; k++){ r.m[i][j] = (r.m[i][j] + (((m[i][k] % mod) * (a.m[k][j] % mod)) % mod)) % mod; } } } return r; } }; martix qpow(martix a, int b){ martix r; for(int i = 0; i < 2; i++){ for(int j = 0; j < 2; j++){ if(i == j)r.m[i][j] = 1; else r.m[i][j] = 0; } } int n = b; for(;n;n=n >> 1){ if(n & 1)r = r * a; a = a * a; } return r; } signed main(){ int x1, x2, a, b, n; cin >> x1 >> x2 >> a >> b >> n; x1 %= mod; x2 %= mod; martix r; r.m[0][0] = b; r.m[0][1] = a; r.m[1][0] = 1; r.m[1][1] = 0; martix t = qpow(r,n - 2); int ans = (((t.m[0][0] * x2) % mod) + ((t.m[0][1] * x1) % mod)) % mod; cout << ans << '\n'; } ``` ::: ![](https://i.imgur.com/ueiNArM.png) --- ### UVA 10870 [題目](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=489&page=show_problem&problem=1811) $f(n) = a_1 f(n - 1) + a_2 f(n - 2) + a_3 f(n - 3) + ... + a_d f(n - d) , (n > d)$ 已知前d項求第n項 這題可以將f(n)的式子列成矩陣，並用矩陣快速冪的方式快速取值 $$ \begin{bmatrix} f(n) \\ f(n- 1) \\ f(n -2) \\ \vdots \\ f(n-d+1) \end{bmatrix}= \begin{bmatrix} a_1 & a_2 & a_3 & \cdots & a_{d-1} & a_d\\ 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & 0 \\ 0 & 0 & 0 & \cdots & 0 & 0 \end{bmatrix} \begin{bmatrix} f(n-1) \\ f(n- 2) \\ f(n -3) \\ \vdots \\ f(n-d) \end{bmatrix} $$ --- :::info :::spoiler <font color="00FF00">**AC**</font>_code UVA 10870 ```cpp= #include<bits/stdc++.h> #define int long long using namespace std; int d, n, mod; struct martix{ int m[16][16]; martix(){ memset(m,0,sizeof(m)); } martix operator *(martix a){ martix r; for(int i = 0; i < d; i++){ for(int j = 0; j < d; j++){ for(int k = 0; k < d; k++){ r.m[i][j] = (r.m[i][j] + ((m[i][k] % mod) * (a.m[k][j] % mod)) % mod) % mod; } } } return r; } }; martix qpow(martix a, int b){ martix r; for(int i = 0; i < d; i++){ r.m[i][i] = 1; } for(;b; b /= 2){ if(b & 1)r = r * a; a = a * a; } return r; } martix a_i, f; signed main(){ while(cin >> d >> n >> mod){ if(d==0 and n == 0 and mod == 0)break; for(int i = 0; i < d; i++){ cin >> a_i.m[0][i]; a_i.m[0][i] %= mod; } for(int i = 1; i < d; i++){ a_i.m[i][i-1] = 1; } for(int i = d - 1; i >= 0; i--){ cin >> f.m[i][0]; f.m[i][0] %= mod; } martix ans = qpow(a_i,n - d) * f; cout << ans.m[0][0] << '\n'; } } ``` ::: ![](https://i.imgur.com/5owJY3M.png) --- # 第五周 ## 預計進度 模運算講義(包含模逆元) 快速冪講義(包含矩陣快速冪) ## 講義 [模運算](/564I9dxSTf6crJP95qRnlQ) [模反元素/模逆元](/zlqbqmRxTiqprniwOmkH6Q) [快速冪&矩陣乘法&矩陣快速冪](/f6LDVf4yTNy-b4vf7kbx9g) # 第六周 ## 本周預計進度 最長遞增子序列LIS DDJ a627 DDJ a628 TIOJ 1907 ### DDJ a627 [題目](http://203.64.191.163/ShowProblem?problemid=a628) 這題就是LIS裸題 這題是a628的側資寬鬆版 可以用DP解 定義a a陣列式題目給的數列 狀態 $dp[i] =$以$a[i]$為結尾的最長遞增子序列的長度 轉移式 $dp[i] = max(所有尾巴小於a[i]的dp)$ 時間複雜度$O(N^2)$ --- :::info :::spoiler DDJ a627 <font color="00FF00">**AC**</font>_code ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ios::sync_with_stdio(0);cin.tie(0); int t; cin >> t; while(t--){ int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; i++){ cin >> a[i]; } vector<int> dp(n); fill(dp.begin(),dp.end(),1); for(int i = 0; i < n; i++){ for(int j = 0; j < i; j++){ if(a[j] < a[i]){ dp[i] = max(dp[j] + 1, dp[i]); } } } int ans = 0; for(int i = 0; i < n; i++){ ans = max(ans,dp[i]); } cout << ans << '\n'; } } ``` ::: ![](https://i.imgur.com/KyPfjnR.png) ### DDJ a628 [題目](http://203.64.191.163/ShowProblem?problemid=a628) 這題就LIS裸題 就用一個一個輸入 如果輸入大於現在LIS的尾巴 那就把輸入接在LIS後 如果輸入小於現在LIS的尾巴 那就把輸入取代LIS中第一個大於輸入的數字 這樣雖然在陣列中的LIS不一定是正確的 但長度是正確的 $O(nlogn)$ --- :::info :::spoiler DDJ a628 <font color="00FF00">**AC**</font>_code ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ios::sync_with_stdio(0);cin.tie(0); int t; cin >> t; while(t--){ int n; cin >> n; vector<int> vc(1); cin >> vc[0]; for(int i = 1; i < n; i++){ int x; cin >> x; if(vc.back() < x){ vc.push_back(x); } else{ auto it = lower_bound(vc.begin(),vc.end(),x); *it = x; } } cout << vc.size() << '\n'; } } ``` ::: ![](https://i.imgur.com/uEhWMGJ.png) ### TIOJ 1907 這題就是剛剛LIS的基礎上加上一開始要sort 和比大小要寬度長度一起比 時間複雜度$O(nlogn)$ --- :::info :::spoiler TIOJ 1907 <font color="00FF00">**AC**</font>_code ```cpp= #include<bits/stdc++.h> using namespace std; bool cmp(pair<int,int> a, pair<int,int> b){ if(a.first != b.first){ return a.first < b.first; } else{ return a.second > b.second; } } int main(){ int t; cin >> t; while(t--){ int m; cin >> m; vector<pair<int, int> > vc(m); for(int i =0; i < m; i++){ cin >> vc[i].first; cin >> vc[i].second; } sort(vc.begin(),vc.end(),cmp); vector<int> x; x.push_back(vc[0].second); for(int i = 1; i < m; i++){ if(vc[i].second > x.back()){ x.push_back(vc[i].second); } else{ auto it = lower_bound(x.begin(),x.end(),vc[i].second); *it = vc[i].second; } } cout << x.size() << '\n'; } } ``` ::: ![](https://i.imgur.com/aZwcUts.png) --- # 第七周週 ## 本週預計進度 最長共同子序列LCS DDJ 310 ### DDJ 310 這題就是單純的LCS 狀態 $f(i,j)$表示$s1[1:i]$和$s2[1:j]$的$LCS$長度 初始轉移 $f(i,0)=f(0,i)=0,i>0$ 轉移式 $f(i,j)= \begin{cases} dp[i-1][j-1]+1 & a[i]=b[j]\\ max(dp[i-1][j],f(i)[j-1]) & \text{else} \end{cases}$ 要壓空間所以要滾動 時間複雜度$O(n^2)$ --- :::info :::spoiler DDJ310 <font color="00FF00">**AC**</font>_code ```cpp= #include<bits/stdc++.h> #define int long long using namespace std; int dp1[100005]; int dp2[100005]; signed main(){ string s,ss; while(cin >> s >> ss){ memset(dp1,0,sizeof(dp1));memset(dp2,0,sizeof(dp2)); for(int i = 1; i <= s.size(); i++){ for(int j = 1; j <= ss.size(); j++){ if(s[i-1] == ss[j-1]){ dp2[j] = dp1[j-1] + 1; } else{ dp2[j] = max(dp2[j-1] , dp1[j]); } } for(int k = 0; k <= ss.size(); k++){ dp1[k] = dp2[k]; } } cout << dp1[ss.size()] <<'\n'; } } ``` ::: ![](https://i.imgur.com/KJ20Zm3.png) --- # 第八週 ## 本週預計進度 製作學習筆記LIS LCS ### 講義 [LIS&LCS](/96ZnugpZRxqkW7LARlrWhg) # 第九週&第十週 ## 本週預計進度 DP背包問題(01背包、有限背包、無限背包) DDJ 279 330 331 ### DDJ 279 [題目](http://203.64.191.163/ShowProblem?problemid=a279) 這題就是01背包 DP存，該重量最大的價值 一個一個物品輸入(設體積V，價值K) 每次輸入都從背包拿出V的體積，並放進當前物體，並判斷原本價值大還是換成當前物體價值大並更新DP 壓成一維時為了保證遍歷$i$可以取到$i-1$的容量對應價值，所以反著遍歷，且為了避免$j - Volume$變負數 轉移式:$dp[j] = max(dp[j], d[j - Volume] + Value)$ --- :::info :::spoiler <font color="00FF00">**AC**</font>_code ddj279 ```cpp= #include<bits/stdc++.h> using namespace std; #define int long long int n, c; int dp[1000005]; signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> c; for(int i = 1; i <= n; i++){ int a, b; cin >> a >> b; for(int j = c; j >= b; j--){ dp[j] = max(dp[j], dp[j - b] + a); } } cout << dp[c] << '\n'; } ``` ::: ![](https://i.imgur.com/cE8S1pr.png) --- ### DDJ 330 有限背包和01背包很像，只是多遍歷一層物品數量 並為了優化複雜度將物品用2的次方分堆 假設現在有7個東西可以放 就分成1 2 4 8個就1 2 4 1 這樣原本遍歷物品個數的複雜度就會降到log --- :::info :::spoiler <font color="00FF00">**AC**</font>_code ddj330 ```cpp= #include<bits/stdc++.h> using namespace std; #define N 1000000 int dp[N+1]; int n,c; int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> c; for(int i = 0; i < n;i++){ int val, v, num; cin >> val >> v >> num; int minn = min(num,c / v); for(int k = 1; minn > 0; k *= 2){ if(k > minn)k = minn; minn -= k; for(int j = c; j >= v * k;j--){ if(j - v * k < 0)continue; dp[j] = max(dp[j],dp[j - v * k] + val * k); } } } cout << dp[c] << '\n'; } ``` ::: ![](https://i.imgur.com/bOwYb3p.png) --- ### DDJ 331 無限背包的概念也差不多 就是一個一個放放到不能放了 轉移式也差不多 --- :::info :::spoiler <font color="00FF00">**AC**</font>_code ddj331 ```cpp= #include<bits/stdc++.h> using namespace std; #define int long long int n, c; int dp[1000005]; signed main(){ cin >> n >> c; for(int i = 0; i < n; i++){ int val, v; cin >> val >> v; for(int j = v; j <= c; j++){ dp[j] = max(dp[j], dp[j - v] + val); } } cout << dp[c] << '\n'; } ``` ::: ![](https://i.imgur.com/pQ1HW3V.png) --- # 第十一週&第十二週 ## 本週預計進度 製作學習筆記DP背包問題 [背包問題](/HWN_qcwZTum7G-qiWgV7DA) # 第十三週 ## 本週預計進度 DP優化(矩陣快速冪) neoj No.776 ## neoj No.776 [題目](https://neoj.sprout.tw/problem/776/) 我們定義$dp[x][i][j]$為$i$花了$x$步走到$j$的方法數 我們可以發現把所有差一步就到$j$的的點的方法數加起來就是到$j$的方法數 所以轉移式$dp[x][i][j] = sigma(dp[x - 1][j][k])k$為所有可以一步走到$j$的點 根據這個轉移式，我們可以再發現把第$x - 1$步的方法數乘上建圖用的鄰接矩陣就可以變$x$步的方法數 定義$DP[x]$是$dp[x]$構成的矩陣 $DP[x] = DP[x - 1][adjacency matrix]$ $DP[0]$大家都只能走到自己，所以$DP[0]就是單位矩陣$ 所以這題的解法就是把鄰接矩陣拿去做矩陣快速密 :::info :::spoiler <font color="00FF00">**AC**</font>_code ```cpp= #include<bits/stdc++.h> #define int long long #define mod 1000000007 using namespace std; int n, m, l; struct matrix { int m[101][101]; matrix(){memset(m,0,sizeof(m));} matrix operator*(matrix a){ matrix r; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ for(int k = 1; k <= n; k++){ r.m[i][j] = (r.m[i][j] + ((m[i][k] % mod) * (a.m[k][j] % mod)) % mod) % mod; } } } return r; } }; matrix qpow(matrix a, int b){ matrix r; for(int i = 1; i <= n; i++){ r.m[i][i] = 1; } for(;b;b >>= 1){ if(b & 1)r = r * a;; a = a * a; } return r; } signed main(){ cin >> n >> m >> l; matrix g; for(int i = 0; i < m; i++){ int x, y; cin >> x >> y; g.m[x][y] = 1; } matrix ans = qpow(g, l); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ cout << ans.m[i][j] % mod; if(j < n)cout << ' '; else cout << '\n'; } } } ``` ::: ![](https://i.imgur.com/HBzrO2Y.png) # 第十四週 ## 本週預計進度 狀態壓縮 TIOJ 1452(新增) neoj No.187(暫時不作) ## TIOJ 1452 [題目](https://tioj.ck.tp.edu.tw/problems/1452) 這題是一題DP+狀態壓縮 每一行的擺放情形用一個整數儲存，該整數的每個bit代表有沒有放置東西 $ex:3 \implies 011$第一和第二有放第三沒放 定義$dp[i][j]$代表第$i$行時，有多少多少種方法可以將該行擺放成$j$二進位表示的情形 我們枚舉每行的所有擺放情形的方法數 轉移過程利用DFS轉移 如果第j個是0，就代表現在要計算的排放方法這格不用放，所以直接向(j+1)遞迴 也就是下面函式中的第二個if 如果第j個是1，就代表要放，分別DFS兩種放法，$1$是放$[i-1][j]、[i][j]$，$2$是放$[i][j]、[i][j+1]$ 也就是下面函是中的第三和第四個if 假設現在要計算110011，那第一個1就有可能和他上面的或是和右邊的組合 如果是要用第一種放法，要把上面的變0(對now操作) 假設現在要計算110011，上一層目前是111111，上一層就要變011111 --- :::info :::spoiler <font color="00FF00">**AC**</font>_code TIOJ 1452 ```cpp= #include<bits/stdc++.h> using namespace std; #define int long long int dp[15][1 << 15]; int n, m; int dfs(int i, int j, int state, int now){ if(j == m){ return dp[i-1][now]; } if(!(state & (1 << j))){ return dfs(i, j+1, state, now); } int ret = 0; if(state & (1 << j)){//這個判斷可以不要寫,上次面的判斷已經篩過相反的情況了 ret += dfs(i, j+1, state, now - (1 << j));//也可以寫成now^(1 << x),因為now的這格bit一定是1 } if(state & (1 << (j+1))){ ret += dfs(i, j+2, state, now); } return ret; } signed main(){ios::sync_with_stdio(0);cout.tie(0); while(cin >> n >> m){ if(n == 0 && m == 0)break; memset(dp,0,sizeof(dp)); dp[0][(1 << m)-1] = 1; for(int i = 1; i <= n; i++){ for(int s = 0; s < (1 << m); s++){ dp[i][s] = dfs(i, 0, s, (1 << m)-1); } } cout << dp[n][(1 << m) - 1] << '\n'; } } ``` ::: ![](https://i.imgur.com/xgnIj7V.png) --- # 第十五週&第十六週 ## 本週預計進度 DP優化(單調對列) zerojudge a146(純單調對列) neoj No.188 No.159(159暫緩) ### zerojudge a146 筆記 [題目](https://zerojudge.tw/ShowProblem?problemid=a146) 這題就是單純的單調列沒有DP 也就是用deque儲存這個框框內有可能有利用價值的數(也就是把數列的位置記下來) 當deque裡的值超出範圍就pop掉 有更大的值出現就把小的pop掉 :::info :::spoiler zerojudge a146 <font color="00FF00">**AC**</font>code ```cpp= #include<bits/stdc++.h> using namespace std; #define int long long int n, k; int a[1000005]; signed main(){ios::sync_with_stdio(0);cout.tie(0); while(cin >> n >> k){ if(k > n)k = n; memset(a,0,sizeof(a)); for(int i = 0; i < n; i++){ cin >> a[i]; } deque<int> qmax;//pos deque<int> qmin;//pos qmax.push_back(0); qmin.push_back(0); for(int i = 1; i < n; i++){ while(!qmin.empty() && qmin.front() <= i - k){qmin.pop_front();} while(!qmin.empty() && a[i] <= a[qmin.back()]){qmin.pop_back();} qmin.push_back(i); if(i >= k - 1){ cout << a[qmin.front()]; if(i < n - 1)cout << ' '; } }cout << '\n'; for(int i = 1; i < n; i++){ while(!qmax.empty() && qmax.front() <= i - k){qmax.pop_front();} while(!qmax.empty() && a[i] >= a[qmax.back()]){qmax.pop_back();} qmax.push_back(i); if(i >= k - 1){ cout << a[qmax.front()]; if(i < n - 1)cout << ' '; } }cout << '\n'; } return 0; } ``` ::: ![](https://i.imgur.com/mNPMbB5.png) ### neoj 188筆記 先不思考如何在這題運用單調對列 先列出一個正確的轉移式 這題40%答案的轉移式很簡單 就在最大容許距離裡找最大價值(要記得減交通成本) 轉移式: $dp[i] = val[i] + max(dp[i - k] ~ dp[i]) - 間隔數量 * c$ 所以就是兩個for迴圈 第一層跑dp 第二層跑區間最大值 :::info :::spoiler 40%code(未進行單調對列優化) ```cpp= #include<bits/stdc++.h> using namespace std; #define int long long int t, n, k, c; int val[100005]; int dp[100005]; signed main(){ cin >> t; while(t--){ memset(dp,0,sizeof(dp)); memset(val,0,sizeof(val)); cin >> n >> k >> c; for(int i = 0; i < n ;i++){ cin >> val[i]; } dp[0] = val[0]; for(int i = 1; i < n; i++){ int maxn = 0; for(int j = 1; j <= k && i - j >= 0; j++){ maxn = max(maxn, dp[i - j] - j*c); } dp[i] = val[i] + maxn; } int ans = 0; for(int i = 0; i < n; i++){ ans = max(ans, dp[i]); } cout << ans << '\n'; } } ``` ::: #### 單調對列優化思路 在40%的code中我們可以發現我們用到的區間最大值 講到區間最大值很容易就想到線段樹 用線段樹優化的確可以，但有更快的方法 就是用上面用到的單調對列儲存區間最大值 :::info :::spoiler neoj NO188 <font color="00FF00">**AC**</font>code ```cpp= #include<bits/stdc++.h> using namespace std; #define int long long signed main(){ int t; cin >> t; while(t--){ int n, k, c; cin >> n >> k >> c; int val[n]; int dp[n]; for(auto &i : val)cin >> i; deque<int> q; dp[0] = val[0]; if(val[0] < 0)dp[0] = 0; for(int i = 0; i < n - 1; i++){ while(!q.empty() && q.front() <= i - k){q.pop_front();} while(!q.empty() && dp[q.back()] + q.back() * c <= dp[i] + i * c){q.pop_back();} q.push_back(i); if(dp[q.front()] - (i + 1 - q.front()) * c > 0){ dp[i + 1] = val[i + 1] + dp[q.front()] - (i + 1 - q.front()) * c; } else{ dp[i + 1] = val[i + 1]; } } int ans = 0; for(int i = 0; i < n; i++){ ans = max(ans, dp[i]); } cout << ans << '\n'; } return 0; } ``` ::: ![](https://i.imgur.com/MzUWZAP.png) ### neoj 159 筆記 # 第十七週&第十八週 ## 本週預計進度 製作DP優化學習筆記(包括資料結構優化) [DP優化](/dvHGezXpRu-SLAj7McPc4A)