# 題目: 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...

# 題目: 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...

# 題目: 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...

# 題目: 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...

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

# 題目: 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...

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

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

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