主題

ZeroJudge - c279: 大家來分解囉~ 解題心得

Not In My Back Yard | 2021-04-05 00:00:01 | 巴幣 0 | 人氣 36

題目連結:


題目大意:
給定一正整數 N (1 ≦ N ≦ 20000),試問 N 最多可以表為多少個相異質數之和?如果不存在任何方法表示為若干個相異質數之和,則輸出 -1。



範例輸入:
18


範例輸出:
3


解題思維:
先建一個質數表(如這題),接著我們將質數視為如這題的金屬棒——每個長度的金屬棒(質數)只能使用一次,看能不能湊到 N。而且就算湊到了 N ,我們用越多金屬棒才是越好。

因此,假設 D[i] 代表 i 之所求解,則對於每個質數 P 之遞迴式為:
D[i] = max(D[i], D[i - P] + C)
D[0] = 0 、 D[1] = -1
其中 C 在 D[i - P] 不為 -1 時等於 1;D[i - P] 為 -1 時等於 0。

因此每個質數跑過一次上面的式子(當然,是按照動態規劃(Dynamic Programming,DP)的精神,跑過的狀態不用重跑)。但是因為每個質數 P 只能用一次,因此我們需要從 i = N 跑到 i = P 為止。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作