###### tags: `選修`
# AP325 練習題單

+ [AP325講義(中正大學 吳邦一教授)](https://drive.google.com/drive/mobile/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m?usp=sharing)
+ [APCS實作題檢測(Facebook)](https://www.facebook.com/groups/359446638362710)
+ [TCFSH CIRC Judge(例題與習題)](https://judge.tcirc.tw/)

<br/>

## 一、遞迴
### 1.1. 基本觀念與用法
### 1.2. 實作遞迴定義
:::info
[d001: 例題 P-1-1. 合成函數(1)](https://judge.tcirc.tw/ShowProblem?problemid=d001)
:::

:::warning
[d002: 習題 Q-1-2. 合成函數(2) (APCS201902)](https://judge.tcirc.tw/ShowProblem?problemid=d002)
+ [題目參考](https://zerojudge.tw/ShowProblem?problemid=f640)
:::

:::info
[d003: 例題 P-1-3. 棍子中點切割](https://judge.tcirc.tw/ShowProblem?problemid=d003)
+ 選每段最接近中點的切割點，會得到最小的切割總成本。
:::

:::warning
[d004: 習題 Q-1-4. 支點切割 (APCS201802) (@@)](https://judge.tcirc.tw/ShowProblem?problemid=d004)
+ [題目參考](https://zerojudge.tw/ShowProblem?problemid=f638)
:::

:::warning
[d005: 習題 Q-1-5. 二維黑白影像編碼 (APCS201810)](https://judge.tcirc.tw/ShowProblem?problemid=d005)
+ [解題參考](https://yuihuang.com/nuts-apcs1071027-3/)
:::

### 1.3. 以遞迴窮舉暴搜
:::info
[d006: 例題 P-1-7. 子集合乘積](https://judge.tcirc.tw/ShowProblem?problemid=d006)
:::

:::warning
[d007: 習題 Q-1-8. 子集合的和 (APCS201810, subtask)](https://judge.tcirc.tw/ShowProblem?problemid=d007)
:::

:::warning
[d008: 習題 Q-1-10. 最多得分的皇后](https://judge.tcirc.tw/ShowProblem?problemid=d008)
+ 先練習 P-1-9. N-Queen解的個數
:::

<br/>

## 二、排序與二分搜
### 2.1. 排序
:::info
[d010: 例題 P-2-1. 不同的數—排序](https://judge.tcirc.tw/ShowProblem?problemid=d010)
+ STL set
:::

### 2.2. 搜尋
:::info
[d011: 例題 P-2-2. 離散化 – sort](https://judge.tcirc.tw/ShowProblem?problemid=d011)
+ 將原陣列a中的相異元素排序在b陣列中，對於原陣列a中的元素，置換成它在b陣列中的index。
+ 在b陣列中找到a[i]可用二分搜加速。
+ 或STL map (map 的元素會按 Key 排序)
+ [離散化](https://meteor.today/article/IeFmpe)
:::

:::warning
d024: 例題 P-2-15. 圓環出口 (APCS202007)
+ 前綴和(prefix sum)
+ 二分搜
+ [解題參考](https://hackmd.io/@emanlaicepsa/APCS202007?fbclid=IwAR167sM5rLEjyCItz0QxNcXz2MjtuWMiH0-9dPHPfJvQWENkfJ0tSR5TVZo#p3)
+ 因為 qi 不會超過 p 的總和，所以將原序列複製一次再求前綴和，可簡化操作。如果沒有此限制，也只需將 qi 預先 mod p的總和即可。

:::

### 2.3. 其他相關技巧介紹

#### 快速冪
:::info
[d012: 例題 P-2-3. 快速冪](https://judge.tcirc.tw/ShowProblem?problemid=d012)
+ [快速冪](https://meteor.today/article/PL8R-c)
:::

#### 模逆元
:::warning
[d017: 習題 Q-2-8. 模逆元 (*)](https://judge.tcirc.tw/ShowProblem?problemid=d017)
+ [費馬小定理](https://www.youtube.com/watch?v=SyK3IXPITco)
+ 若 P 為質數，對任意正整數 a，(a^P-2^ % P) 是 a 在[1, P-1]區間的唯一乘法反元素。
+ [數學上的模逆元](https://meteor.today/article/5hal9d)、[程式設計上的模逆元](https://meteor.today/article/TKXPid)
:::

#### 快速計算費式數列
:::warning
[d014: 習題 Q-2-5. 快速計算費式數列第 n 項](https://judge.tcirc.tw/ShowProblem?problemid=d014)
+ [費氏數列 - 矩陣推導篇](https://puremathcrush.blogspot.tw/2015/09/blog-post.html)
+ [矩陣快速冪加速實作](http://acm.cs.nthu.edu.tw/problem/10322/)
+ [程式設計上的矩陣快速冪](https://meteor.today/article/GEzRKd)
:::

### 2.4. 其他例題與習題

:::info
[d015: 例題 P-2-6. Two-Number problem](https://judge.tcirc.tw/ShowProblem?problemid=d015)
+ 將A陣列與B陣列分別排序，對A中的每一個元素，在B中以滑動的方式找K-a~i~。
+ 或STL set
:::

:::warning
[d016: 習題 Q-2-7. 互補團隊 (APCS201906)](https://judge.tcirc.tw/ShowProblem?problemid=d016)
+ 以一個整數表示一個集合，第i個bit設為1代表第i個字母在集合中。兩個互補團隊的數字 xor 後會等於 2^m^ -1。
+ 若 a xor b = c 則 a xor c = b
:::

:::info
[d020: 例題 P-2-11. 最接近的區間和 (*)](https://judge.tcirc.tw/ShowProblem?problemid=d020)
+ 只用前綴和，O(n^2^) 會 TLE。
+ set+2分搜尋 O(nlog(n))
:::

:::warning
[d021: 習題 Q-2-12. 最接近的子矩陣和 (108 高中全國賽) (*)](https://judge.tcirc.tw/ShowProblem?problemid=d021)
+ 只用前綴和會 TLE。
:::

<br/>

## 三、佇列與堆疊
### 3.1. 基本原理與實作
### 3.2. 應用例題與習題
#### 堆疊
:::info
[d026: 例題 P-3-2. 括弧配對](https://judge.tcirc.tw/ShowProblem?problemid=d026)
:::

:::warning
[d027: 習題 Q-3-3. 加減乘除](https://judge.tcirc.tw/ShowProblem?problemid=d027)
+ [中序式轉後序式](https://market.cloud.edu.tw/content/senior/computer/ks_ks/et/datastruct/compute/compute.htm)
+ 以堆疊1記錄運算元(數字)，堆疊2記錄運算子(+-*/)。
- 遇到運算元就放入堆疊1。
- 遇到運算子則和堆疊2上端的運算子比較優先權，如果比較小，則堆疊2內的運算子先運算。
+ 空的stack執行sk.top()會錯誤
:::

:::info
[d028: 例題 P-3-4. 最接近的高人 (APCS201902, subtask)](https://judge.tcirc.tw/ShowProblem?problemid=d028)
+ 維護一個遞減的序列(前->後或後->前)
+ 均攤分析(amortized analysis) 經典題。
- for迴圈內有while迴圈，但時間複雜度還是O(n)，不會是O(n^2^)，因為雖然while可能某次會做很多次的 pop()，但總共只會做 n 次。
:::

:::warning
[d029: 習題 Q-3-5. 帶著板凳排雞排的高人 (APCS201902)](https://judge.tcirc.tw/ShowProblem?problemid=d029)
+ 最左邊界的無限大高度，初值要超過 2*10^7^
:::

#### 佇列
+ [C++ queue 和 deque的区别](https://blog.csdn.net/qq_25800311/article/details/89060069)
:::info
[d030: 例題 P-3-6. 砍樹 (APCS202001)](https://judge.tcirc.tw/ShowProblem?problemid=d030)
+ 亦有使用堆疊的做法
:::

:::warning
[d036: 習題 Q-3-12. 完美彩帶 (APCS201906)](https://judge.tcirc.tw/ShowProblem?problemid=d036)
+ 滑動視窗，使用queue或deque，模擬區間由左向右滑，左邊出去一個顏色(front pop)，右邊進來一個顏色(back push)。比對queue內相異顏色數量是不是等於M。
:::

#### 滑動視窗(Sliding window)
:::info
[d031: 例題 P-3-7. 正整數序列之最接近的區間和](https://judge.tcirc.tw/ShowProblem?problemid=d031)
:::

:::info
[d032: 例題 P-3-8. 固定長度區間的最大區段差](https://judge.tcirc.tw/ShowProblem?problemid=d032)
+ multiset
+ 亦可用deque會更快
:::

:::warning
[d037: 習題Q-3-13. X差值範圍內的最大Y差值](https://judge.tcirc.tw/ShowProblem?problemid=d037)
:::

:::info
[d033: 例題 P-3-9. 最多色彩帶](https://judge.tcirc.tw/ShowProblem?problemid=d033)
:::

:::info
[d034: 例題 P-3-10. 全彩彩帶 (需離散化或字典) (@@)](https://judge.tcirc.tw/ShowProblem?problemid=d034)
+ 顏色編號可能達到10億，map<int, int>記錄該顏色的數量(key表顏色，value表數量)。(離散化觀念)
+ 因為順序不重要，可用unordered_map查詢會更快。
:::

:::warning
[d035: 習題 Q-3-11. 最長的相異色彩帶](https://judge.tcirc.tw/ShowProblem?problemid=d035)
+ 以queue儲存最長相異色彩帶，往右的顏色如果重複，將queue中此顏色之前的顏色刪除。
:::

<br/>

## 四、貪心演算法與掃瞄線演算法
### 4.1. 基本原理
:::info
[d042: 例題 P-4-1. 少林寺的代幣](https://judge.tcirc.tw/ShowProblem?problemid=d042)
:::

### 4.2. 例題與習題
#### 4.2.1. 單欄位資料排序
:::info
[d043: 例題 P-4-2. 笑傲江湖之三戰](https://judge.tcirc.tw/ShowProblem?problemid=d043)
+ STL sort
:::

:::info
[d044: 例題 P-4-3. 十年磨一劍(最少完成時間)](https://judge.tcirc.tw/ShowProblem?problemid=d044)
+ minimum completion time 經典題
:::

#### 4.2.2. 結構資料排序
:::info
[d045: 例題 P-4-4. 幾場華山論劍(activity selection)](https://judge.tcirc.tw/ShowProblem?problemid=d045)
+ activity selection problem 經典題
:::

:::info
[d046: 例題 P-4-5. 嵩山磨劍坊的問題(加權最小完成時間)](https://judge.tcirc.tw/ShowProblem?problemid=d045)
+ t/w 值小的排在前面，
+ 假設磨a,b之前劍所需的時間為x，則之前的順序，不會影響(a,b)或(b,a)的扣款總額的計算，所以只要考慮a,b順序即可。
- (a,b)-> [x+t(a)]*w(a) + [x+t(a)+t(b)]*w(b) = x(w(a)+w(b)) + t(a)*w(a) + t(b)*w(b) + t(a)*w(b)
- (b,a)-> [x+t(b)]*w(b) + [x+t(a)+t(b)]*w(a) = x(w(a)+w(b)) + t(a)*w(a) + t(b)*w(b) + t(b)*w(a)
- 依兩兩劍(a,b)完成時間*重要性的值排序(a.t * b.w < b.t * a.w)
:::

:::warning
[d047: Q-4-6. 少林寺的自動寄物櫃(APCS201710)](https://judge.tcirc.tw/ShowProblem?problemid=d047)
+ 假設a,b其上物品的重量為x，則這些物品的順序，不會影響(a,b)或(b,a)消耗的能量的計算，所以只要考慮a,b順序即可。
- (a,b)-> x*f(a) + (x+w(a))*f(b) = x(f(a)+f(b)) + w(a)*f(b)
- (b,a)-> x*f(b) + (x+w(b))*f(a) = x(f(a)+f(b)) + w(b)*f(a)
- 依兩兩物品(a,b) 其上重量*頻率的值排序(a.w * b.f < b.w * a.f)
:::

#### 4.2.3. 以PQ處理動態資料(*)
:::info
[d048: P-4-7. 岳不群的併派問題(Two-way merge) (*)](https://judge.tcirc.tw/ShowProblem?problemid=d048)
+ priority_queue< LL, deque<LL>, greater<LL> > pq;
:::

:::warning
[d053: Q-4-8. 先到先服務 (*)](https://judge.tcirc.tw/ShowProblem?problemid=d053)
+ 依輸入序，將其時間與優先佇列中最小值相加後，再放入優先佇列。
:::

#### 4.2.4. 外掛二分搜
:::info
[d049: P-4-9. 基地台 (APCS201703)](https://judge.tcirc.tw/ShowProblem?problemid=d049)
:::

:::warning
[d054: Q-4-10. 恢復能量的白雲熊膽丸](https://judge.tcirc.tw/ShowProblem?problemid=d054)
+ 每次檢測的能量可能 < p[i]。
:::

#### 4.2.5. 掃描線演算法sweep-line
:::info
[d050: P-4-11. 線段聯集 (APCS 201603)](https://judge.tcirc.tw/ShowProblem?problemid=d050)
:::

:::warning
[d051: P-4-12. 一次買賣](https://judge.tcirc.tw/ShowProblem?problemid=d051)
:::

:::warning
[d052: P-4-13. 最大連續子陣列](https://judge.tcirc.tw/ShowProblem?problemid=d052)
+ 配合前綴和，可以做到O(n^2^)，但還是會TLE。
+ 拋棄繼承
:::

:::info
[d055: P-4-14. 控制點(2D-max)](https://judge.tcirc.tw/ShowProblem?problemid=d055)
+ 點的x由小到大序列時，極大點的y是嚴格遞減的。
:::

:::warning
[d056: P-4-15. 最靠近的一對(closest pair) (@@))](https://judge.tcirc.tw/ShowProblem?problemid=d056)
+ [D&C (1)](http://web.ntnu.edu.tw/~algo/Point2.html#3)、[(2)](https://oi-wiki.org/geometry/nearest-points/)、[(3)](https://kknews.cc/code/3aa48ko.amp)
:::

### 4.3. 其他習題

:::warning
[d057: Q-4-16. 賺錢與罰款](https://judge.tcirc.tw/ShowProblem?problemid=d057)
+ Q-4-8 變化題
+ 依工作所需時排序，若相同再依完工時間排序。
:::

:::warning
[d058: Q-4-17. 死線高手](https://judge.tcirc.tw/ShowProblem?problemid=d058)
+ 依完工時間排序。
:::

:::warning
[d059: Q-4-18. 少林寺的櫃姐 (@@)(*)](https://judge.tcirc.tw/ShowProblem?problemid=d059)
:::

:::warning
[d060: Q-4-19. 五嶽盟主的會議場所](https://judge.tcirc.tw/ShowProblem?problemid=d060)
:::

:::warning
[d061: Q-4-20. 監看華山練功場](https://judge.tcirc.tw/ShowProblem?problemid=d061)
:::

<br/>

## 五、分治演算法
### 5.1. 基本原理

### 5.2. 例題與習題
:::info
[d064: P-5-4. 反序數量 (APCS201806)](https://judge.tcirc.tw/ShowProblem?problemid=d064)
:::

:::warning
[a233: 排序法~~~ 挑戰極限](https://zerojudge.tw/ShowProblem?problemid=a233)
+ ZeroJudge Merge Sort
:::

:::info
[d065: P-5-7. 大樓外牆廣告](https://judge.tcirc.tw/ShowProblem?problemid=d065)
+ 以最小高為中間的切割點，如果每次的最低點都在邊緣，例如輸入高度是遞增或遞減，時間複雜度會高到O(n^2^)。
:::

<br/>

## 六、動態規劃
### 6.1. 基本原理
#### 6.1.1. 基本思維與步驟
#### 6.1.2. 狀態轉移
#### 6.1.3. 分類與複雜度
#### 6.1.4. Top-down memoization

### 6.2. 例題與習題
#### 6.2.1. 1D0D
:::info
[d066: P-6-1. 小朋友上樓梯最小成本](https://judge.tcirc.tw/ShowProblem?problemid=d066)
:::

:::info
[d067: P-6-2. 不連續的表演酬勞](https://judge.tcirc.tw/ShowProblem?problemid=d067)
:::

:::info
[d068: P-6-3. 最小監控鄰居的成本](https://judge.tcirc.tw/ShowProblem?problemid=d068)
+ 設dp[i]是前i個點的最小監控成本(最後一點選在i)。
+ dp[i] = c[i] + min(dp[i-1], dp[i-2], dp[i-3]) for i>2
:::

:::warning
[d072: Q-6-4. 闖關二選一](https://judge.tcirc.tw/ShowProblem?problemid=d072)
+ 每個關卡通過的成本只跟上一關有關(跟更早的無關)，設dp[i][j]為第i關、第j種狀態的最低成本(i<=n，j=0或1)。
+ dp[i][j] = min( dp[i-1][0]+abs(pwd[i-1][0]-pwd[i][j]), dp[i-1][1]+abs(pwd[i-1][1]-pwd[i][j]) );
:::

:::warning
[d073: Q-6-5. 二維最大子矩陣](https://judge.tcirc.tw/ShowProblem?problemid=d073)
+ [O(n4)](http://chchwy.blogspot.tw/2008/11/acm108-maximum-sum-ac.html)
+ [O(n3)](http://hanting1225.blogspot.tw/2015/11/uva-108-maximum-sum.html)
:::

#### 6.2.2. 2D0D
:::info
[d069: P-6-6. 方格棋盤路線](https://judge.tcirc.tw/ShowProblem?problemid=d069)
:::

:::info
[d070: P-6-7. LCS](https://judge.tcirc.tw/ShowProblem?problemid=d070)
+ LCS(Longest Common Subsequence，最長共同子序列)，序列分析的重要問題
:::

:::warning
[d074: Q-6-8. Local alignment](https://judge.tcirc.tw/ShowProblem?problemid=d074)
+ LCS
:::

:::info
[d071: P-6-9. 大賣場免費大搬家](https://judge.tcirc.tw/ShowProblem?problemid=d071)
+ 0/1-knapsack 經典題。
:::

:::warning
[d075: Q-6-10. 置物櫃出租 (APCS201810)](https://judge.tcirc.tw/ShowProblem?problemid=d075)
+ 0/1-knapsack
+ 價值和容量相等。
+ dp表格在王老不夠容量的那欄，其值(最大可退的容量)可能還不夠，往後找第1個超過的值。
:::

#### 6.2.3. 1D1D
:::info
[d076: P-6-11. Catalan number](https://judge.tcirc.tw/ShowProblem?problemid=d076)
:::

:::warning
[d084: Q-6-12. 楊鐵心做 1 休 K](https://judge.tcirc.tw/ShowProblem?problemid=d084)
+ P-6-2 的推廣
+ 設dp[i] 是前 i 天可以獲得的最大報酬，dp[i]=max(dp[i-k-1]+當天報酬, dp[i-1])。
+ dp前k天的初值為當天之前報酬的最大值。
:::

:::warning
[d077: P-6-13. 周伯通的基地台 (@@)](https://judge.tcirc.tw/ShowProblem?problemid=d077)
+ P-6-3 的推廣型
:::

:::warning
[d085: Q-6-14. K 次買賣 (106 高中全國賽 subtask)](https://judge.tcirc.tw/ShowProblem?problemid=d085)
+ P-4-12 的推廣型
:::

:::info
[d078: P-6-15. 一覽衆山小](https://judge.tcirc.tw/ShowProblem?problemid=d078)
+ LIS(longest Increasing subsequence，最長遞增子序列)，1D1D經典題
+ [演算法筆記-LIS](http://web.ntnu.edu.tw/~algo/Subsequence.html)
:::

:::warning
P-6-16. 山寨華山論劍
+ P-4-4 加權版本
+ weighted activity selection problem 經典題
:::

#### 6.2.4. 2D1D與其他
:::info
[d079: P-6-17. 切棍子](https://judge.tcirc.tw/ShowProblem?problemid=d079)
:::

:::warning
[d086: Q-6-18. 矩陣乘法鏈](https://judge.tcirc.tw/ShowProblem?problemid=d086)
:::

### 6.3. 進階題(*)

<br/>

## 七、基本圖論演算法
### 7.1. 基本觀念與名詞
### 7.2. 資料結構與基本演算法
#### 7.2.1. 資料結構

#### 7.2.2. BFS

:::info
[d090: P-7-1. 探索距離](https://judge.tcirc.tw/ShowProblem?problemid=d090)
:::

:::warning
[d093: P-7-4. 方格棋盤的最少轉彎數路線](https://judge.tcirc.tw/ShowProblem?problemid=d093)
:::

:::warning
[d094: Q-7-5. 闖關路線 (APCS201910)](https://judge.tcirc.tw/ShowProblem?problemid=d094)
+ [解題參考](https://yuihuang.com/nuts-apcs1081026-3/)
:::

#### 7.2.3. DFS
:::info
[d091: P-7-2. 開車蒐集寶物](https://judge.tcirc.tw/ShowProblem?problemid=d091)
:::

:::warning
[d092: P-7-3. 機器人走棋盤 (APCS 201906)](https://judge.tcirc.tw/ShowProblem?problemid=d092)
+ DFS
:::

:::warning
[d100: Q-7-8. 小寶的著色問題](https://judge.tcirc.tw/ShowProblem?problemid=d100)
+ DFS 或 BFS
+ [二分圖判斷(1)](https://www.itread01.com/content/1545440778.html)、[(2)](https://www.itread01.com/content/1536499328.html)
+ 圖可能不連通，每個點都要遍歷
+ C++ IO加速
:::

#### 7.2.4. DAG與topological sort
:::warning
[d095: P-7-6. DAG 的最長與最短路徑](https://judge.tcirc.tw/ShowProblem?problemid=d095)
:::

:::warning
[d099: Q-7-7. AOV 最早完工時間](https://judge.tcirc.tw/ShowProblem?problemid=d099)
:::

### 7.4. 補充教材(*)
#### 7.4.1. Dijkstra演算法
#### 7.4.2. 併查集(Union and Find)
#### 7.4.3. 最小生成樹

<br/>

## 八、樹上演算法
### 8.1. 基本觀念與名詞
### 8.2. 樹的儲存與基本演算法
#### 8.2.1. 儲存樹的資料結構
#### 8.2.2. DFS
:::info
[d102: P-8-1. 樹上的推銷員](https://judge.tcirc.tw/ShowProblem?problemid=d102)
:::

:::warning
[d103: P-8-2. 物流派送系統](https://judge.tcirc.tw/ShowProblem?problemid=d103)
+ 因為樹沒有環，樹上找距離也可以用DFS(遞迴)，程式會更簡潔。
:::

:::info
[d025: 例題 P-3-1. 樹的高度與根 (bottom-up) (APCS201710)](https://judge.tcirc.tw/ShowProblem?problemid=d025)
+ 子節點因數量不定，可用vector諸存
vector<int> child[100000];
+ [vector二維陣列1](https://ramihaha.tw/c-program-container-vector-array-linklist/)
+ [vector二維陣列2](http://f74461036.pixnet.net/blog/post/274951462-c%2b%2b-vector二維陣列)
+ memset
:::

:::warning
[d106: P-8-7. 寶石的顏色 (108 全國高中賽)](https://judge.tcirc.tw/ShowProblem?problemid=d106)
+ 寶石的顏色號碼不超過10^9^，記錄每一顏色的寶石數用陣列會太大，離散化可以用 [STL map](http://larry850806.github.io/2016/06/06/STL1/#map)。
:::

:::warning
[d111: P-8-14. 血緣關係 (APCS201603)](https://judge.tcirc.tw/ShowProblem?problemid=d025)
+ 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)
:::

#### 8.2.3. BFS
#### 8.2.4. 由下而上的走訪
:::warning
[d104: P-8-3. 購物中心選位置](https://judge.tcirc.tw/ShowProblem?problemid=d104)
+ 計算每個節點孩子的數量，找子節點數量>=n/2者。
:::

:::warning
[d108: Q-8-6. 樹狀圖的距離總和](https://judge.tcirc.tw/ShowProblem?problemid=d108)
+ 需要O(n)的算法，參考 P-8-3 計算median到所有點的距離和的方法。
:::

### 8.3. 例題與習題
#### 二元樹
:::warning
[d105: P-8-5. 自動分裝 (APCS202002)](https://judge.tcirc.tw/ShowProblem?problemid=d105)
+ 二元樹
+ [解題參考](https://yuihuang.com/nuts-apcs1090105-4/) (一邊走就要一邊調整節點重點才不會TLE)
:::

#### 樹的最大獨立集
:::warning
[d107: P-8-8. 樹的最大獨立集](https://judge.tcirc.tw/ShowProblem?problemid=d107)
+ greedy
:::

:::warning
[d109: P-8-11. 公司派對 (NCPC)](https://judge.tcirc.tw/ShowProblem?problemid=d109)
+ 最大權重獨立集
+ DP
:::