若 x 是 質數,且 x 是 第k個質數 同時 k 也是質數的話, x 就是 Super_Prime。

給你 n,求一 Super_prime 序列 [p1, p2, p3, ..., pk] 使得 p1+p2+p3+...+pk=n。

要求 k 越小越好,Super_Prime 可以重複用。

先 make 出 Super_Prime 的序列。

要組合成 n 且  用最少 就是 背包問題。

所以就這樣 背包DP,然後 復原答案。

會有一些情況是無解的,例如 n=1, 2, 4 等,輸出 0。<WA多次後發現= =>

不知道為啥,輸出的序列 不能sort,否則會 WA 掉= =。

我的code

http://codepad.org/WS6HB57c

 

文章標籤
創作者介紹

jghs1328

jghs1328 發表在 痞客邦 PIXNET 留言(0) 人氣()