###### tags: `選修` # 進階程式設計 ## 零、評量方式、學習歷程 1. 上課基本練習 50% 2. [筆試](https://hackmd.io/@cube/BykHYRldu) 30%。 3. 期末作業解題報告 20% - 10~12題。 * 每寫一題10分,上限120分(12題)。 * 每個單元至多可放3題(不可以都寫同一單元的題目)。 - 每題的子標題為 (1) 單元、題號 (2) 解題動態、評分結果截圖 (3) 原始的解題思路(遇到的錯誤) (4) 錯誤程式碼 (5) 正確的解題思路(修正的地方) (6) 正確程式碼 - 檢核方式 * 請儘量放一開始有錯,然後修正的題目。如果你每一題都是一次AC,那你應該是骨骼清奇、萬中無一的練武奇才,應該不用怕老師的檢核吧。 * 如果老師懷疑你的程式是網路複製貼上,會請你當場重寫一次當做檢核,寫不出來作業直接作廢0分,所以作業請務必自思考己完成。 - 可放到學習歷程檔案。 4. 學習歷程檔案 - 最後一週上課結束前如果認證完成,學期總成績加分。 5. 演算法進階參考 - [中央資工演算法](https://staff.csie.ncu.edu.tw/jrjiang/alg2019/) - [中山資工演算法](http://par.cse.nsysu.edu.tw/~cbyang/course/algo/algo_index.htm) - [台大資訊系統訓練班演算法](https://www.csie.ntu.edu.tw/~d92005/course_Algorithm(2008).htm) <br/> :::success **資料結構** ::: ## 一、堆疊 + [常用C++ STL:stack](https://yuihuang.com/cpp-stl-stack/) + C++ 堆疊(Stack)常用的方法 | 名稱 | 意義 | |:-----|:----------| |stack<int> sk |建立一個int型別的stack| |sk.size() |堆疊元素數量| |sk.empty() |判斷堆疊是否為空| |sk.push(x) |從堆疊「頂端」加入一個元素x| |sk.pop() |刪除堆疊頂端元素| |sk.top() |取得堆疊頂端元素| :::info EX_1_1:[a034: 二進位制轉換](https://zerojudge.tw/ShowProblem?problemid=a034) ::: :::info EX_1_2:[b838: 104北二2.括號問題](https://zerojudge.tw/ShowProblem?problemid=b838) + [STL stack](http://larry850806.github.io/2016/06/06/STL1/#stack) + 遇「(」push + 遇「)」檢查stack是否是空的,如果不空pop,如果空,則括號不正確。 ::: ``` c= #include <iostream> #include <stack> using namespace std; int main() { int t; cin >> t; cin.ignore(); while(t--) { .... // 宣告一個存 char 的 stack string s; int cnt=0; cin >> s; for .... // 對s中的每一個字元判斷 { if .... // 如果s[i]是左括號 .... // 將s[i]放到堆疊 else // s[i]是右括號 { if .... // 如果堆疊內有左括號,堆疊size>0 { .... // pop出一個左括號 .... // 計數加1 } else // 沒有左括號,表示式子不正確 { .... // 計數設為0 .... // 跳出迴圈 } } } if .... // 最後堆疊內還有左括號 .... // 計數設為0 cout << cnt << endl; } return 0; } ``` :::warning [b923: stack 堆疊的模板題](https://zerojudge.tw/ShowProblem?problemid=b923) ::: :::warning [d318: 11185 - Ternary](https://zerojudge.tw/ShowProblem?problemid=d318) ::: :::warning [a132: 10931 - Parity](https://zerojudge.tw/ShowProblem?problemid=a132) + 以stack記錄除2的餘數 + stack:push、pop、top ::: :::warning [a565: 2.p&q的邂逅](https://zerojudge.tw/ShowProblem?problemid=a565) + 以getline(cin,line)讀取一行前,用 cin.ignore() 將 n 之後的換行字元讀掉。 + C++ IO加速 ios::sync_with_stdio(false); cin.tie(0); ::: <br/> ## 二、佇列 + [常用C++ STL:queue](https://yuihuang.com/cpp-stl-queue/) + C++ 佇列(Queue)常用的方法 | 名稱 | 意義 | |:--------|:----------| |queue<int> q |建立一個int型別的queue| |q.size() |佇列元素數量| |q.empty() |判斷是否為空| |q.push(x) |從佇列「後端」加入一個元素x| |q.pop() |從「前端」刪除一個元素| |q.front() |取得前端元素| |q.back() |取得後端元素| :::info EX_2_1:[e155: 10935 - Throwing cards away I](https://zerojudge.tw/ShowProblem?problemid=e155) ::: :::info EX_2_2:[a982: 迷宮問題#1](https://zerojudge.tw/ShowProblem?problemid=a982) + [STL queue](https://blog.csdn.net/qq_25800311/article/details/89060069) + [pair](https://blog.csdn.net/sinat_35121480/article/details/54728594) ::: ``` c= #include <iostream> #include <cstring> #include <queue> using namespace std; int main() { int n; while(cin >> n) { char maze[n][n]; int len[n][n]; .... // 宣告一個存放 pair 的 queue memset(len,-1,sizeof(len)); // 將len陣列的初值都設為-1,表示沒走過 for (int i=0;i<n;i++) for (int j=0;j<n;j++) cin >> maze[i][j]; Q.push({1,1}); len[1][1]=1; maze[1][1]='#'; while .... // 當 queue 內還有點 { .... // 讀取 queue 內的點 .... // pop 掉這個點 int r=p.first,c=p.second; if(maze[r+0][c+1]=='.') // 右 { .... // 將 {r,c+1} push 至 queue .... // 右邊點的長度為目前點的長度+1; .... // 右邊點設為 '#' 表示走過 } .... // 下 .... // 左 .... // 上 } if(len[n-2][n-2]==-1) cout << "No solution!\n"; else cout << len[n-2][n-2] << endl; } return 0; } ``` :::warning [e447: queue 練習](https://zerojudge.tw/ShowProblem?problemid=e447) ::: :::warning [d900: NOIP2010 2.接水问题](https://zerojudge.tw/ShowProblem?problemid=d900) + 依輸入序,取佇列中最小值相加後再放入佇列。 ::: :::warning [d406: 倒水時間](https://zerojudge.tw/ShowProblem?problemid=d4060) + BFS,以STL queue實作。 ::: <br/> ## 三、串列 :::info EX_3_1:[陸行鳥大賽車](https://neoj.sprout.tw/problem/21/) + [C++ STL list的初始化、新增、遍歷、插入、刪除、查詢、排序、釋放](https://www.itread01.com/content/1541708352.html) + list:push_back、insert、erase + find,需含入 algorithm 標頭檔 + CodeBlocks C\+\+ 11設定 - Settings / Compiler / Have g++ follow the C\+\+11 ISO C++ language standard Dev-C\+\+:專案 / 專案選項 / 編譯器訊息 / 程式碼產生 / 語言標準(-std)/ISO C\+\+11 ::: ``` c= #include <iostream> #include <algorithm> #include <list> using namespace std; int main() { int n,m,t,x; while(cin >> n) { .... // 宣告可以存放 int 的list(命名為lst) .... // 將 1~n 放入 lst cin >> m; for(int i=0;i<m;i++) { cin >> t >> x; if(t==0) // x受攻擊 { .... // 找到 x 的位置(it) .... // 刪除 x (使用it來刪除) } else if(t==1) // x衡刺 { .... // 找到 x 的位置(it) .... // 將 itp 設為 it 的前一個位置 if .... // 如果 x 不是開頭 (使用 it 來判斷) { .... // 刪除 x (使用it來刪除) .... // 將 x 插入至 itp 所指的位置 } } } .... // 印出 lst 裏的每個元素 cout << endl; } return 0; } ``` :::warning [a870: 10. List Maker](https://zerojudge.tw/ShowProblem?problemid=a870) ::: <br/> <br/> :::success **演算法** ::: ## 一、排序演算法 + [思考排序的演算法](https://zh.wikipedia.org/wiki/十三張) + [Sorting 排序](https://yuihuang.com/sorting/) ### 1. 氣泡排序(Bubble Sort) + [bubble sort](https://medium.com/@mingjunlu/understanding-bubble-sort-7aa4567986ae) :::info EX_1_1:[a539: 10327 - Flip Sort](https://zerojudge.tw/ShowProblem?problemid=a539) ::: ```c= // bubble sort for .... // 6個數字排序只需5個循環 { for .... // 每次比較索引值0 1、1 2、2 3、3 4、4 5的數字 { if .... // 如果左邊比右邊大 { .... // a[j]和a[j+1]交換 cnt++; } } } ``` :::warning [e561: 00299 - Train Swapping](https://zerojudge.tw/ShowProblem?problemid=e561) + 計算 Bubble Sort 交換的次數。 ::: ### 2. 選擇排序(Selection Sort) vs. 交換排序(Exchange Sort)] + [selection sort](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E5%85%A5%E9%96%80-%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F%E8%88%87%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E6%B3%95-23d4bc7085ff):對每個位置的數值,找到其後最小的數值,並進行對調。 + [exchange sort](http://it-easy.tw/sorting-algorithm/) :::info EX_1_2:[d452: 二、直線最小距離和](https://zerojudge.tw/ShowProblem?problemid=d452) (以交換排序 或 選擇排序實作) + 排序後求中位數,中位數與數組各數的距離和最小 + swap() ::: ```c= // selection sort for(int i=0;i<n-1;i++) { int minIdx=i; // 假設目前最小值的index為i for(........) // 從i的右邊開始找最小值的index { if(s[....]<s[....]) minIdx=j; } swap(........); // 把最小值(minIdx的值)和i的數值交換 } ``` ```c= // exchange sort for(int i=0;i<n-1;i++) { for .... // 從 i 的右邊開始找最小值 { if .... // 如果檢查的這個數 < 第 i 個數 { .... // 以 swap 函式交換這兩個數; } } } ``` ### 3. 插入排序(Insertion Sort) + [insertion sort1](https://kopu.chat/2017/06/22/插入排序insertion-sort/):將還未排序的元素插入到已排序數列中的正確位子。 + [insertion sort2](https://jason-chen-1992.weebly.com/home/-insertion-shell-sort) :::info EX_1_3:[a104: 排序](https://zerojudge.tw/ShowProblem?problemid=a104) (以插入排序實作) ::: ```c= // insertion sort for(int i=1;i<n;i++) { int key=s[i],j=i-1; // key(s[i]) 是正在處理的數值,設 j 是 i 的前一個 while .... // 前面的元素(s[?])大於 key,而且 j 沒有小於邊界 { .... // 前面的元素(s[?])比 key 大,所以往右移 .... // j減1 } s[....]=key; // 將key放入正確位置 } ``` :::warning [c010: 10107 - What is the Median?](https://zerojudge.tw/ShowProblem?problemid=c010) + 每次輸入都排序會TLE。 + 以insertion sort的觀念,在已排序的數列中,找出新數字的正確位置。 ::: ### 4. 快速排序(Quick Sort) + [quick sort1](https://ithelp.ithome.com.tw/articles/10202330?sc=iThelpR) + [quick sort2](http://notepad.yehyeh.net/Content/Algorithm/Sort/Quick/Quick.php) ### 5. 合併排序(Merge Sort) + [merge sort1](http://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html) + [merge sort2](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E9%80%B2%E9%9A%8E-%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F%E6%B3%95-6252651c6f7e) ### 6. 排序演算法效率比較 + [Sorting Algorithms Animations](https://www.toptal.com/developers/sorting-algorithms) + [Comparison Sorting Algorithms](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html) + [排序演算法整理](http://notepad.yehyeh.net/Content/Algorithm/Sort/Sort.php) ![](https://i.imgur.com/BYBK9Bh.png) :::warning [a737: 10041 - Vito's family](https://zerojudge.tw/ShowProblem?problemid=a737) + 將所有親戚的門牌號碼排序,中位數即為 Vito 新家的門牌號碼。 ::: :::warning [d150: 11369 - Shopaholic](https://zerojudge.tw/ShowProblem?problemid=d150) + 將商品價格降序(大->小)排序,再取每三個內的最小值。 + for(int i=2;i<n;i+=3) ::: <br/> ## 二、搜尋演算法 :::info EX_2_1:[d732: 二分搜尋法](https://zerojudge.tw/ShowProblem?problemid=d732) + 陣列從index 1 開始存。 + 先試試尋序搜尋會如何? ::: ``` c= #include <iostream> using namespace std; int main() { int n,k; while(cin >> n >> k) { int num[n+1],q; for(int i=1;i<=n;i++) cin >> num[i]; for(int i=0;i<k;i++) { cin >> q; .... // int L=?,R=?,mid; while .... // 左邊界index <= 右邊界index { .... // 計算 mid if .... // 如果找到 { cout << m << endl; break; } else if .... // 中間值 > q .... // 調整右邊界index else // 中間值 < q .... // 調整左邊界index } if .... // 如果 左邊界index > 右邊界index,表示沒找到 cout << 0 << endl; } } return 0; } ``` :::info EX_2_2:[f815: TOI_y21m4_a01遊戲升等](https://zerojudge.tw/ShowProblem?problemid=f815) + [最小值最大化](https://blog.csdn.net/qq_43690454/article/details/104020240) + 對答案二分搜。假設一個答案,檢查這個答案是不是符合條件限制,以二分搜尋的方式逼進最大值。 ::: ``` c= #include <iostream> #include <algorithm> using namespace std; int main() { int n,level[20005]; long long c; cin >> n >> c; for(int i=0;i<n;i++) cin >> level[i]; .... // 排序 int L=0,R=2147483647,ans=0; while(L<=R) { long long sum=0,m=(L+R)/2; .... // 計算升到此等級所需的金幣(sum) if.... // 如果 sum<=金幣 { .... // m 是可能的答案 .... // 增加 L } else .... // 減少 R } cout << ans << endl; return 0; } ``` :::warning [f679: 公會成員](https://zerojudge.tw/ShowProblem?problemid=f679) + 想偷懶,排序可用STL sort,二分搜尋可用lower_bound。 ::: :::warning [c575: APCS 2017-0304-4基地台](https://zerojudge.tw/ShowProblem?problemid=c575) + 對n個服務點排序,並計算服務點兩兩相鄰距離。若要分成K群,則找出前K-1個最大的兩兩相離距離,作為分群切割處。(時間複雜度高) + 實做可用二分搜尋的觀點。因為基地台直徑的答案一定介於1~(最遠服務點-最近服務點)。先假設可能答案為最大最小值中間,測試k個基地台可否覆蓋所有服務點,不行則調整基地台直徑,以二分搜尋法找出答案(直接對答案進行二分搜尋)。 ::: :::warning [c904: 天龍國的蜜蘋果](https://zerojudge.tw/ShowProblem?problemid=c904) + 最大化平均值 + [解題參考1](https://www.twblogs.net/a/5c9e53cabd9eee7523887628) + [解題參考2](https://blog.csdn.net/karry_zzj/article/details/70232097) ::: <br/> ## 三、貪心(greedy)演算法 + 假設一個問題可以藉由一系列的選擇來解決,貪婪演算法為在每一步的選擇中,都採取在當前狀態下的最佳選擇,從而希望導致結果是最佳解的演算法。(短視近利) :::info EX_3_1:[TCFSH CIRC Judge d042: 例題 P-4-1. 少林寺的代幣](https://judge.tcirc.tw/ShowProblem?problemid=d042) ::: ```c= #include <iostream> using namespace std; int main() { int coin[4]={1,5,10,50},m,n; cin >> m; while(m--) { int num=0; cin >> n; for.... // 從 50 元開始換 { .... // 計算可換出的數量 .... // 剩下沒換零錢的金額 } cout << num << endl; } return 0; } ``` :::info [f627: 1. 礦砂採集](https://zerojudge.tw/ShowProblem?problemid=f627) + fractional knapsack + 依單位重量價值由大到小排序(搭配比較函式greater)。 + 不斷將單位重量價值最大的礦砂放入背包,直到背包已滿或沒有礦砂可放入。 + vector、pair ::: ```c= #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n,m; while(cin >> n >> m) { .... // 宣告存放礦沙的 vector for(int i=0,w,p;i<n;i++) { cin >> w >> p; .... // 將{p,w}放入vector } .... // 根據單位重量價值由大到小排序 int sum=0; //礦沙總價值 for .... // 將每個 pair 取出 { if .... // 背包重量 > 此礦沙重量 { .... // 更新總價值(將此礦沙全部放入背包) .... // 背包重量扣掉此礦沙重量 } else // 背包重量 <= 此礦沙重量,沒空間可以放下一個 { .... // 更新總價值(背包剩下的重量全部放此礦沙) break; } } cout << sum << endl; } return 0; } ``` :::warning [a465: 12405 – Scarecrow](https://zerojudge.tw/ShowProblem?problemid=a465) + 遇到可耕種土地時,即在右邊之土地放一個稻草人,並將已被涵蓋的可耕種土地視為不可耕種之土地。 ::: :::warning [e538: 11389 - The Bus Driver Problem](https://zerojudge.tw/ShowProblem?problemid=e538) + 將早晨巴士路線由小->大排序,傍晚巴士路線由大->小排序。( sort搭配比較函式 greater<int>() ) + 最短的早晨巴士路線搭配最長的傍晚巴士路線,會使支付的總加班費最小。 ::: :::warning [f832: 隕石 (Meteorite)](https://zerojudge.tw/ShowProblem?problemid=f832) + 將隕石重量、捕捉器容量排序 + 由捕捉器容量大到小,決定是否可以裝入此時最大重量的隕石。 ::: <br/> ## 四、分而治之(divide & conquer)演算法 ### 1. 步驟 + 分割(divid):將原本的問題分割成多個子問題(規模較小的同類問題)。 + 克服(conquer):當子問題劃分得足夠小時,用相同的演算法遞迴地解決所有的子問題。 + 合併(combine):合併(merge)所有子問題的解答成為原本問題的解答。 :::info EX_4_1:[d219: 00374 - Big Mod](https://zerojudge.tw/ShowProblem?problemid=d219) + [分配律](https://zh.wikipedia.org/wiki/%E6%A8%A1%E9%99%A4) + (A\*B)%M=[ (A%M)\*(B%M) ]%M→B^P^%M=[ (B^P/2^%M)\*(B^P/2^%M) ]%M + EX:4\*5%3=(4%3)\*(5%3)、5\*8%3=(5%3)\*(8%3)%3 ::: :::info EX_4_2:[d153: 六、智力测验](https://zerojudge.tw/ShowProblem?problemid=d153)(以快速排序實作) + 時間複雜度O(n^2^)的排序法會TLE ::: ```c= #include <iostream> using namespace std; void quickSort(int s[],int left,int right) { if(left>=right) return; int i=left,j=right,pivot=s[left]; // 最左邊的元素設為 pivot(基準點) while .... // 將小於 pivot 的元素放在它左邊,大於的放右邊。i==j時停止。 { while .... // 從右「向左」找小於 pivot 的元素。 s[j] >= pivot 且 i<j 時繼續找 j--; while .... // 從左「向右」找大於 pivot 的元素 .... // 將 i 向右移 if(i<j) // 如果找到 (i<j),以 swap 函式,讓小於 pivot 的放左邊,大於 pivot 的放右邊 .... } .... // pivot 交換至中間 .... quickSort(s,left,i-1); // 左半繼續做 quickSort .... // 右半繼續做 quickSort } int main() { int t,n; cin >> t; while(t--) { cin >> n; int s[n]; for(int i=0;i<n;i++) cin >> s[i]; quickSort(s,0,n-1); cout << s[(n-1)/2] << endl; } return 0; } ``` :::warning [d636: 大爆炸bomb](https://zerojudge.tw/ShowProblem?problemid=d636) ::: :::warning [a227: 三龍杯 -> 河內之塔](https://zerojudge.tw/ShowProblem?problemid=a227) + 遞迴 + [河內塔|樂和遊戲](http://www.novelgames.com/zh-HK/tower/) + [河內塔程式參考](http://notepad.yehyeh.net/Content/DS/CH02/4.php) ::: <br/> ## 五、樹搜尋(tree search)與回溯(backtracking)演算法 + 許多問題尋找解答的過程可以表示成樹,建構出解答空間樹(solution space tree),因此找解答就轉變成一個樹搜尋問題。 + DFS vs. 回溯(backtracking) - DFS 會遍訪每一個未拜訪過的節點,如果該節點已無可拜訪的節點,就會退回該節點的父節點再遍訪其它分支的節點。 - backtracking 在進行未拜訪節點選擇時,可以先選擇可能會有好結果的分支,或是提早判斷若無解,就不遞迴至下一層,而是回溯退回先前的節點。(偷吃步) :::info EX_5_1:[d908: 4. 最佳路徑](https://zerojudge.tw/ShowProblem?problemid=d908) + 深度優先搜尋(depth-first search, DFS)演算法 + [相鄰矩陣表示法(Adjacency Matrix)](http://web.ntnu.edu.tw/~algo/Graph.html#3) ::: ```c= #include <iostream> #include <cstring> using namespace std; int graph[26][26],visited[26],mx; void DFS(int now, int sum) { if(sum > mx) mx=sum; for .... //從此點(now) 往下檢查 26 個字母是否相連 if .... // 如果 now 有連到 i ,且 i 還沒走過 { .... // 將 i 設為走過(以 1 表示) .... // 從 i 繼續往下走,路徑的權重總和要加 now->i 這一段的權重 .... // 取消 i 設為走過(以 0 表示),讓其它點可以連到 i } } int main() { char s,u,v; int n,w; while(cin >> s >> n) { memset(graph,0,sizeof(graph)); .... // 將visited 陣列歸 0 mx=0; for(int i=0;i<n;i++) { cin >> u >> v >> w; if( w > graph[u-'A'][v-'A'] ) // 有些線段會重複 .... // 將相鄰矩陣graph[u(轉為數字)][v(轉為數字)]的值設為w,A 轉為 0,B 為 1 …, } .... // 從 s 開始走,路徑的權重總和為 0 cout << mx << endl; } return 0; } ``` :::info EX_5_2:[d324: 00750 - 8 Queens Chess Problem](https://zerojudge.tw/ShowProblem?problemid=d324) + backtracking + 一維陣列queen[8],陣列索引為皇后的col,值為皇后的row。 + [皇后衝突的判斷](https://sites.google.com/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/d324-00750---8-queens-chess-problem) ::: ```c= #include <iostream> using namespace std ; int qr,qc,queen[8],cnt; // index為col,值為row void print() { if(queen[qc-1]==qr-1) // 符合題目皇后必須放的位子 { cout << " " << cnt++ << " "; for(int i=0;i<8;i++) cout << queen[i]+1 <<" "; cout << endl; } } bool attack(int r,int c) { for .... // 檢查是否衝突到之前已擺放的皇后 if .... // 在同一列或對角(abs) return true; // 表示衝突到 return false; } void place(int q) // 填第 q 個皇后,即第幾 col { for .... // 每一列(0~7)都試試看 if .... // 如果放在 r 列, q 欄的皇后不會衝突之前已擺放的皇后 { .... // 記錄此皇后的位置 if(q==7) print(); else .... // 繼續擺下一個皇后 } } int main() { int t; cin >> t; while(t--) { cin >> qr >> qc; cout <<"SOLN COLUMN"<<endl; cout <<" # 1 2 3 4 5 6 7 8"<<endl<<endl; cnt=1; place(0); cout <<endl; } return 0; } ``` :::info EX_5_3:[c812: 1. 觀光景點](https://zerojudge.tw/ShowProblem?problemid=c812) + [相鄰串列表示法(Adjacency Lists)](http://web.ntnu.edu.tw/~algo/Graph.html#4) + [整數最大值可用0x3f3f3f3f](https://blog.csdn.net/jiange_zh/article/details/50198097) + [STL vector](http://larry850806.github.io/2016/06/06/STL1/#vector)、 + [pair](https://blog.csdn.net/sinat_35121480/article/details/54728594) + C++ 11 auto ::: ```c= #include <iostream> #include <vector> using namespace std; vector<pair<int,int>> graph[5000]; bool visited[5000]={0}; int n,vk,q,ans=0,u,v,val; void dfs(int now,int correlation) { .... // 將現在的點(now)設為走過 if(correlation>=q) ans++; for .... // 對每個連到 now 的節點(nxt) if .... // 如果 nxt 沒走過 .... // 從 nxt 繼續往下走,重新估算路徑的相關性 } int main() { cin >> n >> vk >> q; for(int i=0;i<n-1;i++) { cin >> u >> v >> val; graph[u].push_back({v,val}); .... // 無向圖,u 連到 v , v 也連到 u } dfs(vk,0x3f3f3f3f); cout << ans-1 << endl; // 減掉自己 return 0; } ``` :::warning [d626: 小畫家真好用](https://zerojudge.tw/ShowProblem?problemid=d626) + 全域變數 + 分四個方向做DFS ::: :::warning [a290: 新手訓練系列 ~ 圖論](https://zerojudge.tw/ShowProblem?problemid=a290) ::: :::warning [b967: 第 4 題 血緣關係](https://zerojudge.tw/ShowProblem?problemid=b967) + max_element + [解題參考1](https://yuihuang.com/zj-b967/) (farthest of farthest:以任意點(0)為根,找離它最遠的點(v),再以此點(v)為根,找最大深度) + [解題參考2](https://sites.google.com/site/zsgititit/zi-xun-neng-li-jian-ding/apcs/10503di4ti-xue-yuan-guan-xi) ::: :::warning [f161: 3. 尋寶之旅](https://zerojudge.tw/ShowProblem?problemid=f161) + 在 DFS 過程中,每次走到一個節點,就將該點顏色數量加一。當 DFS 返回父節點時,把該點顏色數減一,以表示回復到沒有走到此點的狀態。 + 在拜訪每個節點時,檢查該點的顏色數量有沒有超過最大值。 + 寶石的顏色號碼不超過10^9^,記錄每一顏色的寶石數用陣列會太大,離散化可以用 [STL map](http://larry850806.github.io/2016/06/06/STL1/#map)。 ::: <br/> ## 六、動態規劃(Dynamic Programming、DP) + [DP概念解說](https://hackmd.io/@3xOSPTI6QMGdj6jgMMe08w/HknO-zmQI/https%3A%2F%2Fhackmd.io%2Fs%2FByfT8JZ9E#Week-9-Dynamic-Programming-%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83) ### 1. 零錢問題 + [Money Changing Problem](https://sites.google.com/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/d904) :::info EX_6_1:[d904: 換零錢](https://zerojudge.tw/ShowProblem?problemid=d904) + [整數最大值可用0x3f3f3f3f](https://blog.csdn.net/jiange_zh/article/details/50198097) + memset(a,0x3f,sizeof(a)); 需含入cstring ::: ```c= #include <iostream> #include <cstring> using namespace std; int main() { int C,N; while(cin >> C >> N ) { int coin[N],dp[C+1]; // dp[]存每種金額,最少的硬幣數量 memset(dp,0x3f,sizeof(dp)); dp[0]=0; for(int i=0;i<N;i++) cin >> coin[i]; for .... // 對每一個種硬幣 for .... // 對每一金額(硬幣幣值以上金額),重新檢查硬幣數是否會改變 if .... // 如果拿此硬幣會讓硬幣數量減少 .... // 更新硬幣數量 cout << dp[C] << endl; } return 0; } ``` :::warning [d253: 00674 - Coin Change](https://zerojudge.tw/ShowProblem?problemid=d253) + [解題參考](https://sites.google.com/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/d253-674---coin-change) ::: :::warning [b232: TOI2009 第四題:分房子](https://zerojudge.tw/ShowProblem?problemid=b232) + 將1,3,5,7,9…視為幣值,n間房子視為金額 + f(n)=f(n-1)+f(n-3)+f(n-5)… ::: ### 2. 0-1背包問題 + 有 N 個物品,每個物品有重量 W 跟價值 V,背包最大負重 MAX,求在物品不可以分割不重複的情況下,背包可以裝的最大價值為何? - [圖示](https://labuladong.gitbook.io/algo/mu-lu-ye-2/mu-lu-ye-2/bei-bao-wen-ti) - 如果用窮舉法,N 個物品,每個物品可以選擇拿或不拿,會有 2^N^ 種可能性要考慮,例如 N=20 時,有1048576種排列組合。 + 題目分析 - 如果背包重量 MAX 小一點,或是物品少一些,也許比較容易看出,所以建立一個 dp[N][MAX] 的陣列來做動態規劃。 - dp[i][j]表示只考慮拿前 i 個物品,放入最大負重為 j 的背包時,可以得到的最大價值。 - 狀態轉移方程式 $$ \begin{cases} dp(0,j)=0 \\[2ex] dp(i,j)=max(\ dp(i-1,j),\ dp(i-1,j-w[i]) + v[i]\ ) \end{cases} $$ - 亦即在負重 j 時,第 i 個物品不拿時的價值,與拿了第 i 個物品時的價值(背包剩下的負重為j-w[i],此時的最大價值+v[i]),哪一個較好。 - [步驟說明](https://riptutorial.com/zh-TW/dynamic-programming/example/25787/0-1%E8%83%8C%E5%8C%85%E5%95%8F%E9%A1%8C) :::info EX_6_2:[d637: 路過的鴨duck](https://zerojudge.tw/ShowProblem?problemid=d637) + [解題參考](https://sites.google.com/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/d637-duck) ::: ```c= #include<iostream> #include<cstring> using namespace std; #define N 10000 // 飼料數 #define M 100 // 胃容量(背包容量) int dp[N+1][M+1],c[N],v[N],n; // c[i]表飼料的體積,v[i]表飼料的飽足感(價值) int main() { while(cin >> n) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) cin >> c[i] >> v[i]; for .... // 考慮每一顆飼料要不要吃 for .... // 考慮每一個胃容量的飽足感(價值) if .... // 如果第 i 顆飼料太大超過胃容量(背包容量) .... // 維持一樣(不吃i,同容量)的飽足感(價值) else .... // 第 i 顆飼料可以吃下,則此胃容量的飽足感(價值)為max(不吃i時的飽足感 , 吃i的飽足感+胃容量扣i時的飽足感) cout << dp[n][M] << endl; } return 0; } ``` :::info EX_6_3:[b184: 5. 裝貨櫃問題](https://zerojudge.tw/ShowProblem?problemid=b184) + [空間優化](https://hackmd.io/@3xOSPTI6QMGdj6jgMMe08w/ByfT8JZ9E?type=view#01-%E8%83%8C%E5%8C%85%E5%95%8F%E9%A1%8C) + dp(j)為背包重量為j時的最大價值。 對第 i 個物品,考慮不拿或拿,狀態轉移方程式為 dp(j)=max( dp(j), dp(j−w[i])+v[i] ) j必須為從大到小,否則可能會造成重複拿物品。 ::: ```c= #include <iostream> using namespace std; int main() { int n,v,c; while (cin >> n) { int dp[105]={0}; for .... // 有n個貨物 { cin >> v >> c; for .... // 每讀入一個貨物,即從100往前檢查(比v大的容量才需要檢查) .... // 裝這個貨物的價值比較大,dp[i]就設定成新的(較大的)價值 } cout << dp[100] << endl; } return 0; } ``` :::warning [b140: NOIP2005 3.採藥](https://zerojudge.tw/ShowProblem?problemid=b140) ::: :::warning [b131: NOIP2006 2.开心的金明](http://zerojudge.tw/ShowProblem?problemid=b131) + [解題參考](https://sites.google.com/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/b131-noip2006-2) ::: ### 3. LIS 最長遞增子序列 + [最長遞增子序列(LIS)_1](http://web.ntnu.edu.tw/~algo/Subsequence.html) + [最長遞增子序列(LIS)_2](https://yuihuang.com/dp-lis/) + 若dp[i]表示以num[i]為結尾的最長遞增子序列長度(num[0]~num[i]的LIS長度), 則狀態轉移方程式為dp[i]=max(dp[j])+1,0<=j<i 且 num[j]<num[i]。 :::info EX_6_4:[TCFSH CIRC Judge d078: P-6-15. 一覽衆山小](https://judge.tcirc.tw/ShowProblem?problemid=d078) + [常用C++ STL:vector](https://yuihuang.com/cpp-stl-vector/) + [常用C++ algorithm:lower_bound & upper_bound](https://yuihuang.com/cpp-algorithm-lower-bound-upper-bound/) + [STL max_element](https://shengyu7697.github.io/std-max_element/) ::: ```c= // O(n^2),NA(score:40%) #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; while(cin >> n) { vector<int> p(n); // 戰力值 ... // 宣告一個vector dp,dp[i]表示以p[i]為结尾的最長遞增子序列長度(p[0]~p[i]的LIS長度)。初始化為1(每一個數字本身就是長度為一的 LIS) .... // 輸入戰力值 for .... // 找出 p[i] 能接在哪些數字後面 for .... // 檢查 j=0~i-1 if .... // 如果 p[i]>p[j],表示 p[i] 能接在它後面 .... // dp[j]+1 若大於 dp[i],更新為新長度 .... // dp[]之中最大的值即為 LIS 的長度 } return 0; } ``` ```c= // O(nlog(n)) #include <iostream> #include <vector> using namespace std; int main() { int n; while(cin >> n) { vector<int> lis; for(int i=0,p;i<n;i++) { cin >> p; .... // 在目前 lis 陣列中找 >=p 的最小值,以 p 覆蓋此元素可能產生更長的 LIS if .... // 如果找不到 .... // 將 p 放在 lis 最後 else // 如果找的到 .... // 取代這個值 } cout << lis.size() << endl; } return 0; } ``` :::info EX_6_5:[f608: 4. 飛黃騰達](https://zerojudge.tw/ShowProblem?problemid=f608) + 將點依 x 座標排序後,對 y 座標求LIS。 + 排序時 x 相等則比較 y,可以用 pair 來記錄點,預設即會這樣比較。 + STL [vector(1)](https://zrn-code.github.io/2020/07/19/vector/) [(2)](http://wiki.csie.ncku.edu.tw/acm/course/Vector) + STL [sort、upper_bound](https://zrn-code.github.io/2020/07/23/algorithm/) + STL [pair](https://blog.csdn.net/sinat_35121480/article/details/54728594) ::: ```c= #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; while(cin >> n) { .... // 宣告存pair的vector vector<int> lis; // 存 y 座標的 lis .... // 讀入果實座標 .... .... // 先根據 x 座標排序(小->大),如果 x 座標一樣,再根據 y 座標排序 for .... // 對每個座標 if .... // 如果 lis 是空的,或此點 >= lis 的最後一個元素 .... // 將此點 y 座標放在 lis 最後 else .... // 在目前 lis 陣列中找 >= 此點 y 座標的最小值,以此點 y 座標覆蓋此元素可能產生更長的 LIS cout << lis.size() << endl; } return 0; } ``` :::warning [d242: 00481 - What Goes Up](https://zerojudge.tw/ShowProblem?problemid=d242) + [解題參考](https://yuihuang.com/zj-d242/) + [需多一個 position 陣列](http://web.ntnu.edu.tw/~algo/LongestIncreasingSubsequence.html#3) ::: :::warning [d052: 11456 - Trainsorting](https://zerojudge.tw/ShowProblem?problemid=d052) + [由於火車可以選擇接在前方或後方,所以將原本的數列前接上顛倒的數列](https://yuihuang.com/zj-d052/),再找 LIS。 ::: ### 4. LCS 最長共同子序列 + [最長共同子序列(LCS)_1](https://hackmd.io/@3xOSPTI6QMGdj6jgMMe08w/ByfT8JZ9E?type=view#Longest-Common-Subsequence-LCS) + [最長共同子序列(LCS)_2](https://yuihuang.com/dp-lcs/) :::info EX_6_6:[c001: 10405 - Longest Common Subsequence](https://zerojudge.tw/ShowProblem?problemid=c001) + X陣列的index由0開始,長度i的元素為X[i-1]。 + LCS(0,j)=0 ,LCS(i,0)=0 $$ LCS(i,j)= \begin{cases} LCS(i-1,j-1)+1, if X[i]==Y[j] \\[2ex] MAX(LCS(i-1,j), LCS(I,j-1)), otherwise \end{cases} $$ ::: ```c= #include <iostream> #include <cstring> using namespace std; int dp[1005][1005]; int main() { string s1,s2; while (cin >> s1 >> s2) { memset(dp,0,sizeof(dp)); for .... // s1的所有元素 for .... // s2的所有元素 if .... // s1,s2最後一個元素相同 .... else // s1,s2最後一個元素不同 .... cout << dp[s1.size()][s2.size()] <<endl ; } return 0; } ``` :::warning [a133: 10066 - The Twin Towers](https://zerojudge.tw/ShowProblem?problemid=a133) + [解題參考](http://par.cse.nsysu.edu.tw/~advprog/advprog2013/tip/10066.ppt) ::: :::warning [a252: Another LCS](https://zerojudge.tw/ShowProblem?problemid=a252) :::