问题:超级质数是在质数序列中下标也是质数的质数,例如3,5,11……现在给你一个数,找一个由超级质数构成的最小表示使得这些数的和等于这个数。
解法:先求出这些超级质数,然后就是个完全背包问题。具体可见我动态规划关于背包的文章。
Problem: Super-prime number is such a prime number that its current number in prime numbers sequence is a prime number too. For example, 3,5,11...Your task is to find index of super-prime for given numbers and find optimal presentation as a sum of super-primes.
Solution: At first, calculate all the super-prime you need, then it comes into a complete knapsack problem. You can find more about the topic in my articles.
#include <stdio.h> #include <iostream> #include <cstring> #include <algorithm> using namespace std; #define inf 1010001000 int cnt,pnum,p[10000],q[10000],n,dp[10100],his[10100],k,ans[10100]; bool f[10010]; void output(int x) { if (x<=0) return; ans[++k] = x-his[x]; output(his[x]); } int main() { pnum = 0; memset(f,0,sizeof(f)); for (int i=2;i<=10000;i++) if (!f[i]) { p[++pnum] = i; for (int j=i;j<=10000;j+=i) f[j] = true; } cnt = 0; for (int i=1;i<=pnum;i++) if (p[i]<=pnum) q[++cnt] = p[p[i]]; while (~scanf("%d",&n)) { for (int i=1;i<=10010;i++) dp[i] = -inf; dp[0] = 0; for (int i=1;i<=cnt;i++) for (int j=q[i];j<=n;j++) if (dp[j]<dp[j-q[i]]-1) { dp[j] = dp[j-q[i]]-1; his[j] = j-q[i]; } if (dp[n]==-inf) printf("0\n"); else { printf("%d\n",-dp[n]); k = 0; output(n); sort(ans+1,ans+k+1); for (int i=k;i>1;i--) printf("%d ",ans[i]); printf("%d\n",ans[1]); } } return 0; }