題目出處：Uva
題目連結：10702 - Travelling Salesman
題目大意：有個商人，數個城市(C)，給出從任兩城市之間旅行所可賺取的金錢(A往B和B往A可能不同)、旅途上限(T)、出發城市(S)以及結束城市(E)(可不只ㄧ個)，求所能賺的最高金額。
解題方法：依序更新每次旅途後待在每個城市所能鑽取的最大金額即可，由於有出發城市限制，因此第一次旅途只更新從出發城市(S)出發。
代碼如下：
2015年4月5日 星期日
2015年4月3日 星期五
uva 10700 - Camel trading
題目出處：Uva Online Judge
題目連結：10700 - Camel trading
題目大意：給一串數字（介於1～20）以及加號和乘號組成的計算式，可以自訂優先處理的運算元，求可能的最大值以及最小值。
解題方法：由於都是正整數，因此透過乘號肯定可以讓值變大或者相等。像範例1+2*3*4+5，若是要最大，則優先處理加號，變成3*3*9。若是要最小，則反之，先處理乘號，變成1+24+5。再來就是處理輸入即可。
代碼如下：
題目連結：10700 - Camel trading
題目大意：給一串數字（介於1～20）以及加號和乘號組成的計算式，可以自訂優先處理的運算元，求可能的最大值以及最小值。
解題方法：由於都是正整數，因此透過乘號肯定可以讓值變大或者相等。像範例1+2*3*4+5，若是要最大，則優先處理加號，變成3*3*9。若是要最小，則反之，先處理乘號，變成1+24+5。再來就是處理輸入即可。
代碼如下：
2015年4月2日 星期四
uva 11513 - 9 Puzzle
題目出處：Uva Online Judge
題目連結：11513 - 9 Puzzle
題目大意：有一個九宮格，給一個狀態，問說是否可以透過指令達到由左至右，由上至下為1依序到9。指令分兩大類：水平(H)右移或垂直(V)上移，又分別有三列三行(1,2,3)可以執行。最終要輸出最少移動次數以及移動過程。
解題方法：bfs，從最終狀態開始遍歷所有可能，並將全部結果都紀錄起來。(總共可能數量最多是：9! = 362880 )。由於是從最終狀態往回遍歷，所以要注意過程的紀錄方法。
代碼如下：
題目連結：11513 - 9 Puzzle
題目大意：有一個九宮格，給一個狀態，問說是否可以透過指令達到由左至右，由上至下為1依序到9。指令分兩大類：水平(H)右移或垂直(V)上移，又分別有三列三行(1,2,3)可以執行。最終要輸出最少移動次數以及移動過程。
解題方法：bfs，從最終狀態開始遍歷所有可能，並將全部結果都紀錄起來。(總共可能數量最多是：9! = 362880 )。由於是從最終狀態往回遍歷，所以要注意過程的紀錄方法。
代碼如下：
2015年4月1日 星期三
uva 10000 - Longest Paths
網站荒廢好久了！！！重新開張拉 啾啾
題目出處：Uva Online Judge
題目連結：10000 - Longest Paths
題目大意：有向圖，節點本身無cycle（節點數量上限100），給一個起點，問從起點出發，能走的最遠路徑長度以及終點是啥（若有多條路徑，輸出數值較小的終點）。
解題方法：題目貌似沒寫清楚阿（不然就是我漏看了），任兩點之間最多只有一條邊，用spfa解即可！一開始用了dfs，吃了TLE，忘了邊數最多有101*100/2條，肯定超時的。
代碼如下：
題目出處：Uva Online Judge
題目連結：10000 - Longest Paths
題目大意：有向圖，節點本身無cycle（節點數量上限100），給一個起點，問從起點出發，能走的最遠路徑長度以及終點是啥（若有多條路徑，輸出數值較小的終點）。
解題方法：題目貌似沒寫清楚阿（不然就是我漏看了），任兩點之間最多只有一條邊，用spfa解即可！一開始用了dfs，吃了TLE，忘了邊數最多有101*100/2條，肯定超時的。
代碼如下：
訂閱：
意見 (Atom)