# 題目: UVa 10306 - e-Coins # 題目說明 中文題目說明 # 解題方法 此題為Coin Change問題 定義一個dp[i][j]，代表需要的e-coin數量 轉移方程為dp[i][j] = min(dp[i][j], dp[i - con][j - info] + 1) 最後遍歷所有i與j，找到符合S = sqrt(i*i + j*j)的最小值 # 參考程式碼 #include <iostream> #include <vector> #include <climits> using namesp

# 題目: UVa 357 - Let Me Count The Ways # 題目說明 有5種不同面額的幣值，1、5、10、25、50 給一個N，求由以上幣值組合成N共有幾種方法數 INPUT: 每筆資料輸入一個整數N OUTPUT: 輸出N有幾種組合 # 解題方法 此題為Coin Change問題 先建表，轉移方程為coin[i] += coin[i - j] 其中i為當前的N，j為幣值 之後查表輸出即可 # 參考程式碼 #include <iostream> using namespace std; int main() { ios::s

# 題目: UVa 11463 - Commandos # 題目說明 有一群敢死隊，他們的目的是摧毀所有敵方建築 給一個無向圖，所有edge的weight皆為1 求起點s經過最遠的點後到終點d的最短路徑 題目原意為需要經過所有的點，但是同時有複數個人從起點出發 所以可以改為從起點經過最遠的點最後到終點的問題 INPUT: 第一行輸入一個整數T，代表測資數 每筆測資先輸入兩個整數N與R，代表N個點中有R條線 接下來有R行，每行輸入兩個整數u、v，代表u連到v (雙向) 最後有兩個整數s與d，代表起點與終點 OUTPUT: 輸出起點 -> 最遠的點 -> 終點的最短路徑 # 解

# 題目: UVa 10171 - Meeting Prof. Miguel # 題目說明 給一個有weight的有向圖，圖中的道路有年齡限制 給Y與M的起始點，求Y與M要會合的最短路徑 INPUT: 每筆測資第一行輸入一個整數N，代表接下來有N行 接著輸入四個大寫字元age、connect、u、v，與一個整數w age = Y代表只有年輕人能走的路、age = M代表只有老人能走的路 connect = U為單向連通、connect = B為雙向連通 u連接到v的weight(cost)為w 接下來有兩個大寫字元y與m，前者代表年輕人的起始點，後

# 題目: UVa 821 - Page Hopping # 題目說明 求u與v最短路徑的加總，再除以u與v的組合數 (u與v屬於G中任意兩點) INPUT: 每次輸入兩個整數u與v，代表u連到v，直到u與v為0 若u與v的第一次輸入皆為0，結束程式 OUTPUT: 輸出u與v最短路徑的加總，再除以u與v的組合數 # 解題方法 定義一個vector<vector<int>> G，G[i][j]代表從i到j的最短路徑 先將G中所有元素設為101，相當於無限大 (題目限制範圍為1 ~ 100) 將G[u][v]設為1，代表weight 接下來跑Floyd-Warshal

# 題目: UVa 11495 - Bubbles and Buckets # 題目說明 你需要將一串有N個數字的陣列做排序，每次只能將相鄰的倆倆數字互換 求由Marcelo先手，Marcelo與Carlos輪流做一次互換，誰會完成排序? INPUT: 每筆測資先輸入一個整數N 接著輸入N個數字 (此數字限制範圍為1 ~ N) OUTPUT: 輸出Marcelo與Carlos中誰會勝出 (完成排序) # 解題方法 讀入資料後，利用merge sort將資料做排序 merge sort的時間複雜度為O(n*log n) 每次將陣列中的數字分成兩半，直到剩餘一個數字 再比對倆倆子陣列，按照大

# 題目: UVa 10755 - Garbage Heap # 題目說明 求一個A * B * C大小矩陣的最大子矩陣合 INPUT: 第一行輸入一個整數T，代表測資數 每筆測資第一行輸入三個整數A、B、C 接下來有A * B * C個整數，代表矩陣的值 OUTPUT: 輸出A * B * C大小矩陣的最大子矩陣合 # 解題方法 先建表儲存矩陣的值 將3D最大子矩陣合透過2層迴圈壓縮成2D最大子矩陣合的問題 再將2D最大子矩陣合透過2層迴圈壓縮成1D最大子矩陣合的問題 1D最大子矩陣合問題直接跑Kadane's Algorithm即可 # 參考程式碼 #include <

# 題目: UVa 11951 - Area # 題目說明 有一個N * M大小的矩陣，求子矩陣合 <= K的最大子矩陣範圍 INPUT: 第一行輸入一個整數T，代表測資數 每筆測資第一行有三個整數N、M、K 接下來有N * M個整數，代表矩陣的值 OUTPUT: 輸出子矩陣合 <= K的最大子矩陣範圍 # 解題方法 先建表儲存矩陣的值 將2D最大子矩陣合透過2層迴圈壓縮成1D最大子矩陣合的問題 以一個變數top控制起點，若目前localmax > K則將範圍下移一格 計算目前的範圍及子矩陣合，最後儲存最大的範圍至maxS、最小的值至maxP # 參考

# 題目: UVa 10827 - Maximum sum on a torus # 題目說明 求一個N * N大小矩陣的最大子矩陣合，子矩陣可跨越邊線組合 INPUT: 第一行輸入一個整數T，代表測資數 每筆測資第一行有一個整數N，代表陣列的大小 接下來會有N * N個整數，代表矩陣的值 OUTPUT: 輸出最大的子矩陣合 # 解題方法 先建表儲存矩陣的值 將2D最大子矩陣合透過2層迴圈壓縮成1D最大子矩陣合的問題 利用一個變數st解決左右超出的問題 上下超出的問題可視為整個矩陣 - 最小子矩陣 # 參考程式碼 #include <iostream> #include

# 題目: UVa 12218 - An Industrial Spy # 題目說明 給一個至多7位的數，求每個數字排列後，為質數的數量 例如: 17 可以排成: 1、7、17、71 共有7、17、713個質數 INPUT: 第一行輸入一個整數N，代表測資數 每筆測資輸入一個至多7位的數str OUTPUT: 輸出str排列後，為質數的數量 # 解題方法 先根據題目範圍建質數表1 ~ 10000000 接著跑dfs，找出所有可能的排列並存入result 最後計算質數的數量 # 參考程式碼 #include <iostream> #include <vector