# 題目: UVa 681 - Convex Hull Finding # 題目說明 給 N 個點 (x, y 平面座標)，求這些點的 凸包(Convex Hull) INPUT: 第一行輸入一個整數 T ，代表測資數 每筆測資輸入一個整數 N ，接下來有 N 行，每行輸入兩個點 (x, y) ，為點的座標 輸入一個 -1 間隔測資 OUTPUT: 與輸入幾乎相同 區別在於 N 改為凸包的 node 數量，即分別輸出 node 的座標 起點需輸出 2 次 (頭尾) # 解題方法 能夠使用 Graham's Scan 演算法 或者 Andrew's Monotone...

# 題目: UVa 12125 - March of the Penguins # 題目說明 給一個座標圖，有 N 塊冰塊及數隻企鵝，要使企鵝全部跳到同一塊冰塊上，求哪幾塊可以？ INPUT: 第一行輸入一個整數 T 代表測資數 每筆測資第一行輸入 N 、 D ，代表冰塊的數量、企鵝能跳的距離 接下來有 N 行，每行輸入四個整數 x 、 y 、 n 、 m ，代表點 (x, y) 有 n 隻企鵝，能跳 m 次 OUTPUT: 求哪幾塊冰塊能使所有企鵝跳到上面 # 解題方法 此題的解題概念為 Maximum flow 、 Ford Fulkerson 將 S 連到所有冰塊上，...

# 題目: UVa 11506 - Angry Programmer # 題目說明 給 M 個 node 與 W 條 edge 及他們的 capacity 求此圖的最小割 INPUT: 第一行輸入兩個整數 M 與 W ，代表有 M 個 node 與 W 條 edge 接下來有 M - 2 行，每行輸入兩個整數 U 、 C ，代表 node U 的 capacity 為 C 接下來有 W 行，每行輸入三個整數 U 、 V 、 C ，代表 edge U V 的 capacity 為 C OUTPUT: 輸出此圖的最小割 # 解題方法 此題的解題概念為 Maximum flow 、 Ford...

# 題目: UVa 11380 - Down Went The Titanic # 題目說明 給一個 X * Y 的圖，求 * (人) 能走到 # (終點) 的最大數量 * 碎冰上站著一個人 (起點)， capacity 為 1 . 碎冰， capacity 為 1 @ 厚冰， capacity 為無限 ~ 海， capacity 為 0 # 木頭 (終點)， capacity 為 P INPUT: 輸入三個整數 X 、 Y 、 P 接著輸入 X * Y 個 char OUTPUT: 輸出 * (人) 能走到 # (終點) 的最大數量 # 解題方法 此題的解題概念為 Maximum...

# 題目: UVa 10330 - Power Transmission # 題目說明 給 N 個點， M 條邊，每個點及邊上有 capacity 求此圖的 maximum flow INPUT: 第一行輸入一個整數 N ，接著輸入 N 個整數，代表點 1 ~ N 的 capacity 輸入一個整數 M ，接著有 M 行，每行輸入 U 、 V 、 C 三個整數，代表點 U 與點 V 連線， capacity 為 C 輸入兩個整數 B 、 D 輸入 B 個整數，代表 B 與起點相連 輸入 D 個整數，代表 D 與終點相連 OUTPUT: 輸出 maximum flow #...

# 題目: UVa 12873 - The Programmers # 題目說明 有 P 隊隊伍， S 個組別，每個組別最多能有 C 個隊伍 求參加隊伍的最大數量 INPUT: 第一行輸入一個整數 T ，代表測資數 每筆測資第一行輸入四個整數 P 、 S 、 C 、 m 接下來有 m 行，每行有兩個整數 u 、 v ，代表 u 隊的組別為 v OUTPUT: 輸出參加隊伍的最大數量 # 解題方法 此題的解題概念為 Maximum flow 、 Ford Fulkerson 此題可視為一個 S -> teams -> sites -> T...

# 題目: UVa 11418 - Clever Naming Patterns # 題目說明 有 N 組字詞，裡面分別有 N(K) 個字 你需要從每組字詞中取出一個字，必須按照字母排序 例如題目中的: 3 2 Apples Oranges 1 Bananas 5 Apricots Blueberries Cranberries Zuccini Yams N 為 3 ，所以必須取 3 個字，且開頭須為 A 、 B 、 C 我們取第一組的 Apples 第二組的 Bananas 第三組的 Cranberries 排序後輸出 INPUT: 第一行輸入一個整數 T...

# 題目: Uva 820 - Internet Bandwidth # 題目說明 求 S 到 T 的最大流量 INPUT: 每筆測資第一行輸入一個整數 N ，代表 node 的數量 第二行輸入三個整數 S 、 T 、 C 接下來有 C 行，每行有三個整數 u 、 v 、 w ，代表 u 連到 v ， capacity 為 w 當 N 為 0 時結束程式 OUTPUT: 輸出 S 到 T 的最大流量 # 解題方法 此題的解題概念為 Maximum flow 、 Ford Fulkerson 先建表，按題目要求存為雙向 接著跑 Ford Fulkerson ，每次用 dfs 找到一條 S...

# 題目: UVa 10534 - Wavio Sequence # 題目說明 給一個長度為 n 的整數序列，求此序列的 LIS 與 LDS 相連最長為多少 LIS 的結尾與 LDS 的開頭為同一個字 LIS 的長度與 LDS 相同 INPUT: 每筆測資輸入一個整數 n ，代表序列長度 接下來輸入 n 個整數 OUTPUT: 輸出相同長度且相連的最大 LIS 與 LDS 的合 # 解題方法 若使用普通 DP 的方式找 LIS 與 LDS 會超時，所以使用 greedy algorithm 加速 分別找出 LIS 與 LDS 與每個元素的位置 ( LDS 的找法為反向做 LIS...

# 題目: UVa 11517 - Exact Change # 題目說明 給一個 price 與 N 個面額，求這些面額加總最接近 price (大於等於) 的值與面額數量 INPUT: 第一行輸入一個整數 T ，代表測資數 每筆測資輸入兩個整數 price 與 N 接下來有 N 個整數，代表面額 OUTPUT: 輸出面額加總最接近 price (大於等於) 的值與面額數量 # 解題方法 此題為 Coin Change 問題 以一個 sum 來判斷最少需要做到多少，也就是所有大於 sum 的面額及加總都忽略 轉移方程為 dp[j] = min(dp[j], dp[j -...