演算法解題(1)
以C++為主，部分題目增加或使用Python解
本校進階程式設計課程包含演算法解題(1)與演算法解題(2)，屬於上課範圍會在標題左側加上星號(*)，內容包含認識與實作STL函式庫、排序演算法、模擬、貪婪演算法、遞迴與深度優先搜尋、分而治之與二元搜尋、動態規劃演算法、圖論。評分標準為平時成績占70％，包含作業、出缺席、課堂表現，兩次上機實作共占30％。課程目標為APCS第1到2題(三級分)。
111學年度高二進階程式設計課程
C++ STL(4週)
排序(2週)
模擬(2週)
貪婪(1週)
遞迴(1週)
暴力、枚舉(1週)
分而治之(1週)
二分搜尋(1週)
APCS一小時作業
*APCS202001 第1題猜拳 模擬 2022.11.7
前言
*ch0 C++ STL
(1)stack
*(上課)練習題uva12100 - Printer Queue模擬Queue運作
*(作業)練習題UVa 11987 - Almost Union-Find 當作圖來處理
+(作業)練習題 c073-uva101-TheBlocksProblem vector或linkedlist
APCS201902第3題函數運算式求值 使用deque模擬堆疊 2022.11.13
*(上課)練習題105北市賽-5-手續費
*(作業)練習題uva 136 - Ugly Numbers使用priority queue紀錄下一個要選出來的數，使用set判斷是否曾經出現過
+(作業)練習題UVa1203 - Argus 優先權佇列 2021/1/24
+(難題，特殊解)練習題UVa 11997 - K Smallest Sums 優先權佇列+多個陣列合併 2021/1/24
(4)set
*(上課)練習題acm 10815 - Andy's First Dictionary大寫轉成小寫，非英文字母轉空白，使用set紀錄單字
*(作業)練習題uva11572 - Unique Snowflakes使用L與R紀錄子字串的左右邊界，使用set記憶目前in[L]到in[R]的數字， 當新加入L[R]與set中元素重複，就記錄目前的L-R的值是否比較大，依序從set中刪除in[L]往後的元素刪除直到L[R]不重複，繼續讀取L[R]以後的字元
+(作業)練習題10391 - Compound Words找出複合字，set與字串處理
APCS201810第4題置物櫃出租 模擬、集合 2022.11.16
(5)multiset
*(上課)練習題UVa11136Hoax or what
+(作業)練習題UVa11020 Efficient Solutions
練習題 APCS202301第4題機器出租 排序+模擬+multiset 2023.03.24
*(上課)練習題 uva-540 - Team Queue queue，使用map與deque模擬團體排隊團體插隊，同d718: Waiting In Line
*(作業)練習題uva-156 – Ananagrams 利用vector紀錄所有單字，使用map<string,int>決定此單字轉成小寫排序後的出現次數
*(作業)練習題uva11572 - Unique Snowflakes-map使用pre[]記憶數字中重複出現的數字，之前出現的位置，map<int,int>用於紀錄數字出現的最後位置協助產生pre[]，輸入數字時隨時更新。使用L與R紀錄子字串的左右邊界，掃描pre[]產生最長不重複的數字串的長度。
練習題 APCS202101 第3題切割費用 map
練習題 APCS202109 第3題幸運數字 遞迴、map 2022.10.28
練習題 APCS201906 第3題互補CP 位元運算、map 2022.11.10
練習題 APCS201906 第4題美麗的彩帶 模擬、雙指標、map 2022.11.10
練習題 APCS201902第2題紅白彩帶 map與multiset 2022.11.13
練習題 APCS201902第4題帶著板凳排雞排的高人 map與二分搜 2022.11.14
+(難題)練習題uva-1592-Database使用map將每一個資料庫資料string分別轉成int儲存到db[][]
+練習題12166 - Equilibrium Mobile以天秤第一層來看，第二層的值乘以2就是第一層需要的值 ，第三層的值乘以4就是第一層需要的值，依此類推
練習題uva814 - The Letter Carrier's Rounds使用map紀錄伺服器主機名稱與該主機的使用者清單
(7)綜合練習
(難題)練習題 UVa12096 - The SetStack Computer 將整數集合轉換成整數，將此整數加入集合，達成集合內有集合
*(作業)練習題acm-uva-10474-Where is the Marble sort+lower_bound
練習題APCS202401第1題 遊戲選角 一維陣列 + 排序 2024.01.11 C++
練習題 APCS 10510第1題三角形辨別 排序與條件判斷
練習題uva-10763 - Foreign Exchange分別排序起點與終點，比較已排序的起點與終點陣列
練習題uva-1595 - Symmetry二維空間的直線對稱軸，排序與模擬
練習題 c010: acm-10107 What is the Median? 取中位數，陣列
練習題 d150:acm-11369 – Shopaholic排序取第3k個
練習題 b159: NOIP2007 2.纪念品分组 排序、最大與最小的和
練習題 b162: NOIP2007 1.统计数字 排序 統計每個數的出現頻率
練習題 d452: 直線最小距離和 排序後 最大減最小，次大減次小…
練習題 d190: acm-11462 - Age Sort 2000000個值得排序
練習題acm-10041-Vito's Family 排序取中位數，求中位數到各點絕對值的和
練習題acm-10258-Contest-Scoreboard計算各比賽隊伍的解題個數與penalty time，進行排序
練習題acm-uva-400 - Unix ls行優先列印資料，每一列可能都列印不到最後一行
練習題 UVa 11292 - Dragon of Loowater 排序 2020/10/06
練習題 UVa 11729 - Commando War 排序 2020/10/07
練習題 UVa11300 - Spreading the Wealth 排序 取中位數 2020/10/09
練習題 UVa11039 Building designing 排序+upper_bound 2021/11/22
練習題 UVa10905 - Children's Game 2021/12/12
多鍵值排序
*(上課)練習題 c012: acm-10062Tell me the frequencies! 多鍵值排序，使用struct與algrithm中sort，但ACM輸出的最後一行只能一個endl，不能兩個endl
*(作業)練習題 APCS10503第3題線段覆蓋長度 多鍵值排序、掃描線演算法
練習題 111技藝競賽程式設計 Problem I 字元出現次數 多鍵值排序 Python 2023.01.29
練習題 c044: acm-10008 What's Cryptanalysis 多鍵值排序，使用struct與algrithm中sort
練習題 b083: npsc-2007國中組決賽 D. MVP多鍵值排序，使用struct與algrithm中sort
練習題 acm-10194 - Football (aka Soccer) ，很經典的題目，多鍵值排序，使用struct與algrithm中sort 同b083: npsc-2007國中組決賽 D. MVP
練習題 b158: NOIP2007 1.奖学金 先排序總分，再排序語文，若相同者座號小的優先
(1)APCS的第一題與第二題都是模擬居多
練習題 APCS202306第1題 路徑偵測模擬 模擬 2023.06.18
練習題 APCS202301第1題程式考試 模擬 2023.03.24
*練習題 APCS202210 第1題巴士站牌 模擬
*練習題 APCS202206 第1題數字遊戲 陣列 2022.10.21
*練習題 APCS202201 第1題程式交易 模擬，時間進行
*練習題 APCS202111 第1題修補圍籬 模擬、陣列 2022.10.25
*練習題 APCS202109 第1題七言對聯 模擬、一維陣列 2022.10.28
*練習題 APCS202101 第1題購買力 模擬、一維陣列
*練習題 APCS202010 第1題人力分配 模擬、迴圈 2022.11.2
*練習題 APCS202007 第1題購物車 模擬 2022.11.4
*練習題 APCS202001 第1題猜拳 模擬 2022.11.7
練習題 APCS201906 第1題籃球比賽 模擬 2022.11.10
練習題 APCS201806第1題特殊編碼 (類似題) 模擬 2022.11.17
練習題 APCS10610第1題邏輯運算子 模擬，位元運算與條件判斷
練習題 APCS10603第1題秘密差 模擬，字串處理
練習題 APCS10510第1題三角形辨別 模擬，排序與條件判斷
練習題 APCS10503第1題成績指標 模擬，排序
使用陣列紀錄狀態，善用函式組織程式，好的程式規劃讓程式更容易撰寫
練習題 APCS202401第2題 蜜蜂觀察 二維陣列 +模擬 2024.01.11 C++
練習題 APCS202306第2題 特殊位置 二維陣列 暴力2023.06.18
*練習題 APCS202210 第2題運貨站 二維陣列 模擬
*練習題 APCS202206 第2題字串解碼 字串 2022.10.21
*練習題 APCS202111 第2題動線安排 模擬、二維陣列 2022.10.25
*練習題 APCS202007 第2題骰子 模擬，找出規則 2022.11.4
*練習題 APCS202109 第2題魔王迷宮 模擬、二維陣列 2022.10.28
*練習題 APCS202101 第2題流量 模擬、二維陣列
*練習題 APCS202010 第2題 人口遷移 模擬、二維陣列
*練習題 APCS202201 第2題贏家預測 模擬
*練習題 APCS202301第2題造字程式 二維陣列+模擬 2023.03.24
練習題 APCS201906 第2題機器人的路徑 陣列、模擬 2022.11.10
練習題 APCS10610第2題交錯字串 模擬，字串處理
練習題 APCS10603第2題小群體 模擬，陣列與迴圈
練習題 APCS10510第2題最大和 模擬，二維陣列
練習題 APCS10503第2題矩陣轉換 模擬，二維陣列
練習題 APCS10603第3題數字龍捲風 模擬，陣列與迴圈
練習題 APCS10510第3題定時K彈 模擬，約瑟夫問題（Josephus Problem）
練習題 APCS10510第4題棒球遊戲 模擬
(2)跟數字有關 的模擬
*(上課)練習題 c039-acm: The 3n + 1 problem
*練習題 a828 北市賽 102-1 間隔數 ( number )
練習題 北市賽100-2-疊倍數（Multiple） 從最左邊每個位數除以k求餘數，無法整除，則乘以10加上d。
練習題 c060:-acm-392 Polynomial Showdown數學多項式的表示法，依照題意解題
(3)模擬時間的經過造成狀態改變
*(上課)練習題 d889 北市賽 99 2-黑傑克(jack)
*(作業)練習題 c086: M*A*S*H-acm-402 隔幾個人淘汰一人，算出最後留下來的位置
練習題 a829 北市賽 102-2 主機排程（schedule）
練習題 a830 北市賽 102-5 超級細菌(bacteria)
練習題 acm-10050-Hartals 用陣列模擬罷工計算罷工天數，五六不罷工
練習題 acm - 10191 - Longest Nap 使用陣列紀錄那些分鐘沒有工作，計算最長的沒有工作的時間
(4)模擬各種紙牌、西洋棋與象棋遊戲
*(上課)練習題 10205 - Stack 'em Up 布克牌洗牌，使用stl的map
練習題 d368-10196-Check the Check西洋棋計算國王是否會被吃掉
練習題 acm-10315-Poker-Hands判斷撲克牌誰贏，同花順、鐵支
練習題uva-246-10-20-30 stl與模擬
(5)跟字串有關的模擬
*(上課)練習題 UVa489 - Hangman Judge 猜單字遊戲
練習題 c106-acm271 Simply Syntax 文字組成判斷，是否符合語法
練習題acm 10152 – ShellSort 字串比較，由目標順序與原始順序由最下層比較，依目標順序最下層到最上層，找尋原始順序中符合的順序標示出來，再將目標順序中不符合的顯示出來。
練習題 d017: AB Circle 一串a與b字串中切割成兩段，頭尾可以連接起來，計算其中a與b的個數
(6)其他模擬
練習題 acm-10142-Australian Voting將最少票刪除後，將最少票數選票的第一位刪除，該選票第二位改為第一位
練習題 acm-10033-Interpreter模擬指令執行
練習題 d045- acm: 11222 - Only I did it!找出解別人沒解的題目最多者
練習題11093 - Just Finish it up模擬
練習題 c094-acm-661: Blowing Fuses 模擬整個電器開關過程中最大電流。
練習題uva-12174 - Shuffle模擬，滑動視窗 ，以第一首歌可以出現在1到s個位置的可能性，到底又幾種可能
練習題uva-957-Popes區域長度為Y內的最多個數、個數最多區域的起始點與終止點
練習題104北市賽 大黑馬
練習題103北市賽得分高手
練習題10510第4題棒球遊戲
練習題106北市賽格鬥大賽
練習題106北市賽數字密碼鎖
練習題UVa 1388 - Graveyard n個點分配給n+m個點 2020.10.9
*(上課)範例練習題1 c134-UVa- Parliament
*(上課)範例練習題2 105北市賽 手續費 Huffman編碼
*(上課)範例練習題3 c110: Packets
*範例練習題4 APCS10610第4題物品堆疊 貪心
*範例練習題5 APCS202001 第3題砍樹 貪婪與堆疊 2022.11.7
*範例練習題6 APCS202111 第3題生產線 差分、貪婪
練習題uva-10954 - Add All Huffman編碼
練習題UVa 11491 - Erasing and Winning 2024.01.03
練習題UVa11925 Generating Permutations 2024.01.06
練習題UVa1614 - Hell on the Markets 2024.01.06
練習題UVa1615 - Highway 2024.01.07
練習題UVa1153 - Keep the Customer Satisfied Greedy與Priority Queue 2024.01.07
練習題uva11134 - Fabled Rooks Greedy與Priority Queue
練習題 uva-120- Stacks Of Flapjacks 先將目前未排序中最大的煎餅flip到最上面，再flip到應該到的位置
練習題uva-11054 - Wine trading in Gergovia Greedy第一個進來的數就是要運送來的數量，這個數量運送到下一個點累加到第二個點，就是第二個點的成本，第二點累加值再到第三個點去累加
練習題uva-11269 - Setting Problems依照 (a.f+max(a.s,b.f)+b.s)與b.f+max(b.s,a.f)+a.s，較小的置於前面，優先取
練習題UVa10382 - Watering Grass 2021.12.12
練習題UVa-1606 - Amphiphilic Carbon Molecules 向量外積、貪婪 2023.1.27
ch4暴力 brute-force-使用迴圈(ch5遞迴與深度優先搜尋其實也是一種暴力演算法)
*(上課)練習題 d267: 11577 - Letter Frequency 字串出現頻率
*(上課)練習題 UVa10394 - Twin Primes 求20000000以內所有質數，n與n+2皆為質數 使用篩選法求質數。
*練習題 APCS202001 第2題矩陣總和 枚舉、二維陣列 2022.11.7
*練習題APCS201906第4題美麗的彩帶 滑動視窗(雙指標)、map 2022.11.10
*練習題APCS202206 第4題內積 枚舉、貪婪
*練習題c081-acm-102-Ecological Bin Packing 列出所有可能性
*練習題uva-665-zerojudge-c095-False coin暴力法，若相等的表示天平兩邊都是真幣。若不相等需要記錄天平兩邊的硬幣編號，兩邊總共有n個硬幣，任能確定n-1個是真幣，則就能確定剩下一個是假幣。若總共硬幣為n個，若確定n-1個是真幣，則剩下一個一定是假幣。
練習題uva12325 - ZombiesTreasureChest 暴力法，列出所有可能性
練習題uva-725 – Division暴力列出分母的所有可能性小於10^5，乘以n倍，檢查分子分母是否包含0~9，每個數字都一個
練習題uva-11059 - Maximum Product列舉s[]的起始索引值到中止索引值中所有元素的乘積，起始索引值到中止索引可以相同
練習題 UVa 1602 - Lattice Animals 2023.1.2 列舉網格數i的所有動物網格，找出動物網格的每一個點，列舉每一個點的上下左右的新增點，不能是原本網格內的點，原本動物網格加上此新增點，產生新的動物網格，判斷是否經由旋轉、鏡射、平移可以獲得，則不能加入，否則加入網格數i+1的動物網格集合。
練習題 d139: Compressed String 字元、出現次數
練習題 uva1354Mobile Computing 枚舉
練習題UVa10570 - Meeting with Aliens 暴力 枚舉 2024.01.09
練習題UVa11536 - Smallest Sub-Array 暴力雙指標 2024.01.11
練習題 a011- 幼稚園的算數遊戲 算一算每行有幾個字（word）。Word的定義是連續的字元（letter: A~Z a~z）所組成的字。
練習題 uva 10252 Common Permutation 計算兩個字串字母出現頻率，找出字母頻率較小的。
練習題c088: 00516 - Prime Land 質因數分解
練習題uva-10791 - Minimum Sum LCM，質因數分解，每個因數與該因數的指數當成一個數字的和最小。n=1，結果為2；當質因數只有一個數字，結果為n+1；n=2147483647,是質數，結果為n+1，使用int會溢位。
練習題UVa 11464 - Even Parity 暴力法，列出所有可能性 2020.10.10
練習題 uva-10976 - Fractions Again 列出所有可能性
(遞迴單元教學影片)
*(上課)推薦題 c002:-acm-10696 f91 純粹遞迴
*(上課)推薦題 UVa11384 - Help is needed for Dexter 簡化為f(n) = f(n/2) + 1 2020.10.10
推薦題 APCS201810第3題DF-expression 遞迴 2022.11.15
推薦題 APCS201802第3題支點切割 前綴和與後綴和、遞迴 2022.11.18
推薦題 APCS201902第3題函數運算式求值 運算式+遞迴 2022.11.13
*推薦題 c129:acm-572-Oil Deposits 地圖+遞迴 求最大面積
練習題 d165: 八、草场普查 同c129遞迴求最大面積
練習題acm-10267 - Graphical Editor 模擬圖片處理，F指令需使用DFS走訪
練習題a017: 五則運算 使用遞迴求解加減乘除求餘數運算
練習題a664: 四則運算 使用遞迴求解加減乘除運算
練習題acm-10940 - Throwing cards away II 找出遞迴關係
*ch6 暴力--使用遞迴或其他方式走訪所有可能性(C++)
(教學簡報)
(遞迴單元教學影片)
*(上課)推薦題 c074: Lotto acm 441 列出所有可能排列
*(上課)推薦題 d324:acm-750 - 8 Queens Chess Problem 8Queen DFS
*推薦題APCS201810第2題子集合的和 遞迴、枚舉、暴力 2022.11.15
練習題 APCS202109 第3題幸運數字 遞迴、map 2022.10.28
挑戰題 APCS201910 第4題刪除邊界 (1)遞迴 (2)DP 2022.11.9DP解 2023.3.27遞迴解
挑戰題 APCS202111 第4題真假子圖 DFS、並查集、二分圖 2022.10.25
練習題uva524 - Prime Ring Problem 建立1到31的質數表，DFS走訪列舉16!，若有相鄰點和不是質數，就返回，減少遞迴的次數
練習題 UVa140 - Bandwidth 列出所有可能排列
練習題 UVa1603-Square Destroyer 2023.11.19
練習題 UVa 208 - Firetruck 2023.11.22
練習題 UVa 225 - Golygons 2023.11.24 暴搜 城市不能重複拜訪
練習題 UVa211 - The Domino Effect 2023.11.27 暴搜
練習題 UVa12113 - Overlapping Squares 2023.11.30 暴搜
練習題 UVa11214 - Guarding the Chessboard 2023.12.7 暴搜
練習題 c104: acm-167-The Sultan's Successors 8Queen DFS
練習題 111技藝競賽程式設計 Problem M格雷碼 遞迴 Python 2024.01.29
練習題acm-10267 - Graphical Editor 模擬圖片處理，F指令需使用DFS走訪
練習題 d115-數字包牌 列出所有可能排列
練習題acm-843 - Crypt Kicker 利用字典找出26個字母加密前後對應的可能性，有衝突就倒退。
練習題uva129 - Krypton Factor 將最後加入的字元比較是否成為簡單字串，DFS往下增加字串長度
練習題a229-括號匹配問題 列出所有配對的刮號
練習題d436-10098-Generating Fast, Sorted Permutation列出所有重複排列
練習題北市賽 97 2 萬用字元（wildcard）
練習題北市賽 97 4-食字路口 (Crossroad)
練習題北市賽102 6-任意門 (Transporter)
練習題北市賽103-4-太空迷走
分而治之(Divide And Conquer)
*(上課)練習題uva374 - Big Mod b的p次方%m
練習題 APCS201806第4題反序數量 分而治之 2022.11.17
練習題 d636: 大爆炸bomb a的b次方%10007
練習題uva1608 - Non-boring sequences利用map找出每個元素最近的相同元素的左邊索引值到L[]，找出每個元素最近的相同元素的右邊索引值到R[]，用於在O(1)時間內判斷是否在指定範圍內出現一次的元素，從左邊與右邊往中間找，第一個就找到演算法為O(n)，中間才找到為O(n*log(n))
練習題uva-12627 - Erratic Expansion，若r小於等於2^(k-1)，則f(k,r)=2*f(k-1,r) ，否則f(k,r)=2*3^(k-1)+2*f(k-1,r-2^(k-1))
練習題uva 11495 Bubbles and Buckets找出大數在小數前面的個數。
*(上課)練習題APCS10603第4題基地台
*(上課)練習題uva 1152 - 4 Values whose Sum is 0，a[]與b[]相加後每個數儲存到ab[]，-c[]與-d[]相加後每個數儲存到cd[]，排序ab[]與cd[]，經由將ab[]每個元素使用二元搜尋cd[]中相同值個數累加起來就是答案
推薦題 APCS202007 第3題圓環出口 前綴和、二分搜 2022.11.4
推薦題 APCS202301第4題機器出租 排序+multiset+二分搜(lower_bound)
推薦題 APCS201902第4題帶著板凳排雞排的高人 map與二分搜 2022.11.14
練習題 APCS202206 第3題雷射測試 模擬與二分搜尋 2022.10.16
練習題 APCS202201 第3題數位占卜 字串分割、排序、二元搜尋
練習題 APCS202201 第4題牆上海報 二元搜尋
練習題 APCS202210第4題蓋步道 二分搜尋+BFS
練習題 APCS202101 第3題切割費用 map、二分搜 2022.10.30
練習題uva-12097-Pie將pie平均分給F+1個人，pie若太小可以不考慮分配出去，不可以將幾個pie的碎屑合成一塊，請問最大面積。使用二元搜尋考慮各種面積的可能性，使用函式決定該面積是否可行。
練習題 UVa1648 - Business Center 數學分析與二分搜尋 2024.03.06
練習題 uva1644 - Prime Gap質數與二分搜尋
練習題uva714-CopyingBooks二分搜尋找出能將m個數字切割成k群的數值，Greedy演算法由右邊到左邊，以剛剛二分搜尋獲得的數值進行分群，盡量分給右邊
練習題1471 - Defense Lines，二元搜尋，num[]為輸入的數列，f[i]表示num[i]為終點，連續最長遞增序列長度，s[i]表示num[i]為起點，連續最長遞增序列長度，m[j]，j為f[i]的最小的陣列num值，此m[]陣列數值一定是遞增，m[1]開始儲存。列舉num[i]，找尋num[i]在m[]的lower_bound減去(m+1)，就是左邊的最長長度，加上s[]就是最後長度，紀錄此長度的最長。
練習題uva10539 - Almost Prime Numbers利用篩選法找出1000000以內的質數，將所有質數的二次方、三次方...小於10^12以內的n次方都加入陣列中，排序陣列，使用二元搜尋左邊界與右邊界，輸出左右邊界相減的個數。
練習題UVa 12124 - Assemble 二元搜尋，取符合金額的最大品質數 2020.10.11
練習題UVa 1335 Beijing Guards 二元搜尋+Greedy 2020.10.27
練習題UVa1422 - Processor 二元搜尋+Greedy 2021.12.14
*ch9 動態規劃(Dynamic Programming)演算法
練習題 APCS202401第4題 合併成本 DP-Matrix Chain Multiplication的變形 2024.01.12
練習題 APCS202109 第4題美食博覽會 DP
練習題 APCS202010 第3題勇者修煉 DP
練習題 APCS201910 第4題刪除邊界 DP 2022.11.9
練習題 APCS201802第4題階梯數字 查表，DP，類似巴斯卡三角形 2022.11.20
(1)費氏數列
*(上課)練習題 d544北市賽 98 1-algae 費氏數列
練習題 d212 東東爬階梯 費氏數列
練習題 d038: 900 - Brick Wall Patterns 費氏數列
96北市賽b127: 會議中心（Room）費氏數列
其他數列
練習題 a111: 12149 – Feynman n=k F[k]=F[k-1]+k*k
(2)01 knapsack
*(作業)練習題 d890-3-禮物分配(gift) 北市賽 99 01 knapsack
練習題 d390: 562 - Dividing coins 01 knapsack 類似d890-3-禮物分配(gift)
練習題 b116: TOI2008 3. 加減問題 與99北市賽d890-3-禮物分配(gift) 相同 01 knapsack
練習題 d637: 路過的鴨duck 01 knapsack
練習題 b131: NOIP2006 2. 开心的金明 01 knapsack稍微變化
練習題 d645: 輪下亡魂 01 knapsack混和版 有一個、t個、無限多個
練習題uva-12563-JinGeJinQuhao 01背包 歌曲數目最多，最多中唱最久，時間為背包負重能力，價值為1
練習題UVa242 - Stamps and Envelope Size 類似無限物品個數的背包問題
(3)換零錢
*(上課)練習題 d904: 換零錢
練習題 d133:ACM Q357: Let Me Count The Ways 同 d119: 有獎徵答：換零錢
b205: D. 沙之國 換零錢問題
(4)LCS (Longest Common Subsequence)
*(上課)練習題 104北市賽 舞會 LCS
(作業)練習題 100北市賽-3-蛋白質序列比對（Protein）LCS
(作業)練習題 a252: Another LCS 三個字串的lcs
練習題 a133: 10066 - The Twin Towers LCS
練習題 UVa10723 - Cyborg Genes 2024.02.14
(5)LIS與LDS
*(上課)練習題 b006: 95高雄市資訊能力競賽-矩形旋轉
練習題 APCS202101 第4題飛黃騰達 排序+LIS
練習題 d052-acm-11456 – Trainsorting LIS與LDS
練習題 c115:acm-437 The Tower of Babylon
練習題UVa10635 - Prince and Princess找尋兩數列的最長共同子序列，轉換成最長遞增子序列
練習題 111技藝競賽程式設計 Problem N進步獎 LIS Python 2024.01.30
(6)樹狀結構DP
練習題uva12186 - Another Crisis 樹狀結構dp與dfs，計算每個節點的b個小孩，每個小孩請願書個數須達多少加入到vector p，排序陣列p取前m=(b*T-1)/100+1個相加回傳，樹葉節點回傳1
練習題UVa1220 - Party at Hali-Bula
(7)記憶化DP
練習題 UVa10118 - Free Candies 2024.02.04
練習題 UVa10285 - Longest Run on a Snowboard 2024.02.04
練習題 UVa1629 - Cake slicing 2024.02.08
(8)其他DP
練習題 UVa1626 - Brackets sequence 區間DP 2024.01.21
練習題 UVa1331 - Minimax Triangulation 區間DP 2024.01.21
練習題 uva-1025 - A Spy in the Metro
練習題uva11584 - Partitioning by Palindromes，dp[i]表示s[1]到s[i]最少迴文個數，若s[j]到s[i]是迴文，則dp[i]=min(dp[i],dp[j-1]+1) j=1..i
練習題uva11400 - Lighting System Design dp[i]表示1到i種燈泡的最少花費 2024.01.17
練習題 b018-npsc-2006-高中Lighting System Design組決賽-F-營地
練習題 d042: 11420 - Chest of Drawers
練習題uva-116- c100: Unidirectional TSP 由右邊向左邊將右邊一行的將三個最小的加到左邊一行，且使用re[][]紀錄右邊是第幾個加入的，若最小值相同紀錄最小的列索引值到re[][]，字典順序輸出
練習題 b024: 2006npsc高中組決賽 F. 假日的奇想曲
練習題 d378: 最小路徑 dp[i][j]=min(dp[i-1][j],dp[i][j-1])+map[i][j];
練習題 d482: 方格取数 dp[i][j]=max(dp[i-1][j],dp[i][j-1])+map[i][j];
練習題 uva -10051 - Tower of Cubes
練習題 uva-10237–Bishops 同 861 - Little Bishops只是n值比較大到30
練習題 uva-10039–Railroads
練習題 uva-10198 – Counting
練習題 uva-10131- Is Bigger Smarter?
練習題 uva-10069 Distinct Subsequences
練習題 uva-10154 - Weights and Measures
練習題 d810:大朋友下樓梯 可以一次下1、2、3階
練習題 d686:uva 10003: Cutting Sticks cost[x][y]記錄x到y的最小cost，不重複求取，若計算過就直接回傳 ，關係為cost[left][right]=min(cost[left][right],dp(left,cut[i])+dp(cut[i],right)+right-left)，cut[i]為介於left與right的所有點。 cost[][]先初始化為很大的值 cost[x][y]中間沒有cut，cost[x][y]=0。
練習題 d759-uva-10271-Chopsticks
練習題 a042平面圓形切割
練習題 北市賽 97 3 - 調和三角（triangle）
練習題 uva 1347 – Tour dis[i][j]表示第一條走到最後一點第i點，而走到最後一點第j點，目前已經從第0點走到(第i點與第j點數值較大的點)，每個點都走過一次的最短距離
練習題uva12034 - Race dp[i][j]為i匹馬有j種名次，dp[i][j]=dp[i-1][j]*j+dp[i-1][j-1]*j dp[i-1][j]第i匹馬可以有j種名次的選擇，dp[i-1][j-1]第i匹馬可以選j種名次之一個前，i-1匹馬可以選剩下的j-1個名次，f(n)=dp[n][1]+dp[n][2]+...+dp[n][n]，dp[0][0]=1,其餘初始化為0
練習題uva1213 - Sum of Different Primes質數與DP
練習題uva1645 – Count，a[i]等於累加每個a[k]，k為(i-1)的所有因數
練習題uva-12063-Zeros and Ones，DP，a[len][one][mod]，len數字長度，one數字1的個數，mod餘數，a[1][1][1%k]=1，數字長度至少為1，至少一個1(開頭不能是0)，餘數是1，有一個。末尾補0，a[len+1][one][(mod<<1)%k]+=a[len][one][mod]；末尾補1，a[len+1][one+1][((mod<<1)|1)%k]+=a[len][one][mod]。n為奇數或k等於0，結果為0。
練習題 UVa1394 And Then There Was One 約瑟夫問題DP解 2020.11.22
練習題UVa10891 - Game of Sum 記憶優化DP，列舉區間 2020.1.22
練習題UVa11825 - Hackers Crackdown DP，二進位表示集合2020.1.23
ch10 暴力後進行優化範例(可跳過)
練習題 UVa 11078 - Open Credit System 2020.10.12
練習題UVa1121-SubSequence 2020.10.12
練習題UVa 11549 - Calculator Conundrum 使用Floyd Cycle Detection Algorithm 2020.10.12
練習題UVa 1330 - City Game 使用掃描法取最大矩陣面積 2020.11.7
附錄1 C++語言struct結構 結構的進階應用
練習題acm-11991-EasyProblemfromRujiaLiu 重複數字計算第k個v值出現在第幾個，自訂struct，使用array紀錄數值v的總個數，與累加個數
附錄2 使用C++ class封裝資料與程式
練習題UVa1400 - Ray, Pass me the dishes segment tree
附錄3 除錯