Cutting Sticks! 傳送門 Uva10003 題目概述 給一根給定長度的棍子，還有切割點。 每次切割的花費會是棍子的長度，問要將切割點全部切完，最少需要多少花費。 解題想法 剛開始先思考，如何確定最優解的第一刀落在哪裡？一定是在第 i, j 個斷點之間的某個斷點 k ，也就是要找到某個 k, 且使得這一刀是最佳解（在這裡把棍子的開頭和結尾也當作斷點）。延伸這個想法到 (i, k), (k, j) 兩個部分，這兩個部分變為原題目的子問題，得到兩邊最小花費相加的最小值，再加上原先 (i, j) 切一刀的花費（注意：cost(i, j) 當 時，，因為不用切），就是總共最小花費。因此間單地遞迴下去即可得到最佳解。 $$f(i,j) = cost(i, j) + \mi... Read more 12 Mar 2017 - 3 minute read
Prime! 傳送門 POJ3641 題目概述 求出題目定義的 Pseudoprime。 若 p 不是質數，但對於某個 a 和 前述的 p ，有 的特性，稱 p 是 base-a 的 Pseudoprime。 解題想法 先建質數表，先判斷 p 是否為質數，再判斷是否有 程式碼: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #include <iostream> #incl... Read more 12 Mar 2017 - 1 minute read
Factor! 傳送門 POJ3421 題目概述 求出X 的 Factor chain。 解題想法 先解出 X 的因式分解，最大的 X-factor chain 長度就是指數項相加，該長度的 chain 種類即是所有組成 X 的質因數的組合數（在這裡若分解得到 可以看成 2,2,2 的序列）。 先求出階層，再求組合數會是個好主意。 程式碼: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include <... Read more 12 Mar 2017 - 1 minute read
Semi-prime H-numbers 傳送門 POJ3292 題目概述 一個數字是 H-number 的定義是，它是正整數且可以寫成 4n+1 (n為大於等於 0 的整數) 的形式。 H-number 只有三種， unit、H-prime、H-composite， 1 是唯一的 unit ， H-prime 的定義是，若一個 H-number 不是 unit 且只能被分解為以下形式 ，否則，這個數字即為 H-composite。 還有一個定義叫做 H-semi-prime ，就是一個 H-number 可以被洽兩個 H-prime 相乘組成。 現在，給一個 H-number H ，問介於 [1, H] 有多少個 H-semi-prime ？ 解題想法 使用篩法，先建出題... Read more 12 Mar 2017 - 1 minute read
BFS! 傳送門 POJ3126 題目概述 給兩個四位整數，若要從一個數變到另一個數，一次只能修改一個 Digit ，而且修改後的值必須是質數，問從一個質數到另一質數最少需要幾次修改。 解題想法 先求出質數表，再對質數的狀態做 BFS ，一次修改一個 Digit ，就可以求出一個質數到另一質數的最小修改次數。 程式碼: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 6... Read more 12 Mar 2017 - 1 minute read