#42044: C++ 解題思路


s12270@kcis.com.tw (Ethan Chiu邱柏叡)

學校 : 康橋雙語學校
編號 : 251645
來源 : [118.163.88.49]
最後登入時間 :
2024-06-21 19:26:25
n131. p3. 質數切割法 -- 110新北市資訊學科能力複賽 | From: [118.167.19.240] | 發表日期 : 2024-09-22 15:14

簡單來說就是先計算 2 ~ L(輸入的 int)之間所有的質數(利用雙重 for 迴圈)並把這些質數存下來

再寫出 DP 迴圈(個人是用遞迴,不確定是否有其他解法)依序檢查存下來的質數中是否有任何質數可以用來切割當前的數字

可以使用 lower_bound 或 binary_search 來確認一個質數是否可用來切割(就是檢查 [當前數字 - 當前質數] 是不是質數)

如果可以切割就紀錄每個切法的結果 [dp(第一個質數) + dp(第二個質數) + 當前數字] 然後比較結果找到最小成本的切法

 如果無法切割的話就回傳 0

寫完 dp 的迴圈後把輸入的數字丟進去就好跟算好的質數丟進去就行了

加油!祝解題順利 有問題可以在下面回覆

 
ZeroJudge Forum