題目連結：11407 - Squares
題目大意：link(luckycat)
解題方法：用dp的方法，從小的開始更新，只要能夠由兩個較小的組成，且需要的數字量較少，就更新即可。
注 意：無。
代碼如下：
2015年7月8日 星期三
uva 11407 - Squares
題目出處：Uva
題目連結：11407 - Squares
題目大意：link(luckycat)
解題方法：用dp的方法，從小的開始更新，只要能夠由兩個較小的組成，且需要的數字量較少，就更新即可。
注 意：無。
代碼如下：
題目連結：11407 - Squares
題目大意：link(luckycat)
解題方法：用dp的方法，從小的開始更新，只要能夠由兩個較小的組成，且需要的數字量較少，就更新即可。
注 意：無。
代碼如下：
2015年6月5日 星期五
uva 11401 - Triangle Counting
題目出處：Uva
題目連結：11401 - Triangle Counting
題目大意：link(luckycat)
解題方法：透過dynamic programming的方法，若要討論使用1~N的邊，則會是使用1~N-1的情況加上有使用N的情況(當然此時，N會是最大邊)。
以N = 10為例子。三條邊可以為（由左至右是由小到大）：
邊a 邊b 邊c 幾種組合
2~8 9 10 7
3~7 8 10 5
4~6 7 10 3
5~5 6 10 1
因此，以邊長10為最大邊的情況，可以透過等差級數(S)去計算。
S = a1 + (a1+d) + (a1+2*d) + ... + (a1+(n-1)*d)
= a1*n + ((n-1)+0)*(n)/2*d
= a1*n + (n-1)*n/2*(-2)
= a1*n - (n-1)*n
= n*(a1-n+1)
a1是首項(N-3)，d是公差(-2)，n是數量((a1+1)/2)。
因此，dp[i] = dp[i-1] + S
注 意：需要化簡，過程中才不會overflow。
代碼如下：
題目連結：11401 - Triangle Counting
題目大意：link(luckycat)
解題方法：透過dynamic programming的方法，若要討論使用1~N的邊，則會是使用1~N-1的情況加上有使用N的情況(當然此時，N會是最大邊)。
以N = 10為例子。三條邊可以為（由左至右是由小到大）：
邊a 邊b 邊c 幾種組合
2~8 9 10 7
3~7 8 10 5
4~6 7 10 3
5~5 6 10 1
因此，以邊長10為最大邊的情況，可以透過等差級數(S)去計算。
S = a1 + (a1+d) + (a1+2*d) + ... + (a1+(n-1)*d)
= a1*n + ((n-1)+0)*(n)/2*d
= a1*n + (n-1)*n/2*(-2)
= a1*n - (n-1)*n
= n*(a1-n+1)
a1是首項(N-3)，d是公差(-2)，n是數量((a1+1)/2)。
因此，dp[i] = dp[i-1] + S
注 意：需要化簡，過程中才不會overflow。
代碼如下：
uva 11384 - Help is needed for Dexter
題目出處：Uva
題目連結：11384 - Help is needed for Dexter
題目大意：link(luckycat)
解題方法：這題滿有趣的，我們將N個數每次不停的分兩堆，然後使兩堆有所對應的值，持續進行下去。以N = 6為例子:
1 2 3 4 5 6
^^^^^ (-3)
1 2 3 1 2 3
^^^ ^^^ (-2)
1 0 1 1 0 1
^ ^ ^ ^ (-1)
0 0 0 0 0 0
透過分成一樣的兩堆，兩邊進行同樣的動作，即可算出最少的操作次數。至於為什麼分成兩堆是optimal，可以好好的思考一下～。
注 意：無
代碼如下：
題目連結：11384 - Help is needed for Dexter
題目大意：link(luckycat)
解題方法：這題滿有趣的，我們將N個數每次不停的分兩堆，然後使兩堆有所對應的值，持續進行下去。以N = 6為例子:
1 2 3 4 5 6
^^^^^ (-3)
1 2 3 1 2 3
^^^ ^^^ (-2)
1 0 1 1 0 1
^ ^ ^ ^ (-1)
0 0 0 0 0 0
透過分成一樣的兩堆，兩邊進行同樣的動作，即可算出最少的操作次數。至於為什麼分成兩堆是optimal，可以好好的思考一下～。
注 意：無
代碼如下：
uva 11369 - Shopaholic
題目出處：Uva
題目連結：11369 - Shopaholic
題目大意：link(luckycat)
解題方法：很水的一題，思路是每三個就有一個能不用付錢，要省下最多的錢，那就盡量的讓越大的商品被省下越好。因此，先由大到小排序所有物品，再每三個一起付錢，每次能省下的肯定是當下能省的最多錢（greedy）。
注 意：無
代碼如下：
題目連結：11369 - Shopaholic
題目大意：link(luckycat)
解題方法：很水的一題，思路是每三個就有一個能不用付錢，要省下最多的錢，那就盡量的讓越大的商品被省下越好。因此，先由大到小排序所有物品，再每三個一起付錢，每次能省下的肯定是當下能省的最多錢（greedy）。
注 意：無
代碼如下：
uva 11310 - Delivery Debacle
題目出處：Uva
題目連結：11310 - Delivery Debacle
題目大意：link(luckycat)
解題方法：分析組合的情況。x代表空，o代表一單位的蛋糕，z代表為L形的蛋糕。
F[i]代表完整個寬度2長度i的組合數量，將他化簡成最左邊是填滿的情況。
F[i] = F[i-1] + 2*G[i-1] + 2*F[i-2]
x x x x o x x x z z x x o z x x
= + +
x x x x o x x x z x x x z z x x
後兩個可以上下顛倒，因此要乘二。
G[i]代表缺一個，而總長度為i的組合數量。
G[i] = F[i-1] + F[i-2]
x x x x z x
= +
x x x o x x z z x
給定初始的F跟G即可解決此題。
注 意：運算最大到10^18
代碼如下：
題目連結：11310 - Delivery Debacle
題目大意：link(luckycat)
解題方法：分析組合的情況。x代表空，o代表一單位的蛋糕，z代表為L形的蛋糕。
F[i]代表完整個寬度2長度i的組合數量，將他化簡成最左邊是填滿的情況。
F[i] = F[i-1] + 2*G[i-1] + 2*F[i-2]
x x x x o x x x z z x x o z x x
= + +
x x x x o x x x z x x x z z x x
後兩個可以上下顛倒，因此要乘二。
G[i]代表缺一個，而總長度為i的組合數量。
G[i] = F[i-1] + F[i-2]
x x x x z x
= +
x x x o x x z z x
給定初始的F跟G即可解決此題。
注 意：運算最大到10^18
代碼如下：
2015年4月5日 星期日
uva 10702 - Travelling Salesman
題目出處：Uva
題目連結：10702 - Travelling Salesman
題目大意：有個商人，數個城市(C)，給出從任兩城市之間旅行所可賺取的金錢(A往B和B往A可能不同)、旅途上限(T)、出發城市(S)以及結束城市(E)(可不只ㄧ個)，求所能賺的最高金額。
解題方法：依序更新每次旅途後待在每個城市所能鑽取的最大金額即可，由於有出發城市限制，因此第一次旅途只更新從出發城市(S)出發。
代碼如下：
題目連結：10702 - Travelling Salesman
題目大意：有個商人，數個城市(C)，給出從任兩城市之間旅行所可賺取的金錢(A往B和B往A可能不同)、旅途上限(T)、出發城市(S)以及結束城市(E)(可不只ㄧ個)，求所能賺的最高金額。
解題方法：依序更新每次旅途後待在每個城市所能鑽取的最大金額即可，由於有出發城市限制，因此第一次旅途只更新從出發城市(S)出發。
代碼如下：
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)