SGU 116 Index of super-prime-白红宇

SGU 116 Index of super-prime

阅读量：7041 次

发布时间：2019-06-28

本文共 2768 字，大约阅读时间需要 9 分钟。

SGU_116

一开始用回溯写了一下，发现效率还是很高的，但需要注意不是当前选择的越大就一定越好。

后来看了别人的题解提到了dp的解法，于是便又用dp写了一下，用f[i]表示i最少可以分解为几个超级素数之和，同时用fa[]记录下决策的过程即可。

//回溯 #include
     
       #include
      
        #define MAXD 10010 #define INF 0x3f3f3f3f int N, isprime[MAXD], prime[MAXD], p, sprime[MAXD], sp, a[MAXD], ans[MAXD], num; void prepare() {
   int i, j, k;     memset(isprime, -1, sizeof(isprime));     p = 0; for(i = 2; i <= 10000; i ++) if(isprime[i])         {
               prime[++ p] = i; for(j = i * i; j <= 10000; j += i)                 isprime[j] = 0;         }     sp = 0; for(i = 2; i <= p; i ++) if(isprime[i])             sprime[++ sp] = prime[i]; } void dfs(int t, int cur, int s) {
   int i, j; if(cur >= num) return ; if(s == 0)     {
           num = cur; for(i = 0; i < cur; i ++)             ans[i] = a[i]; return ;     } for(i = t; i > 0; i --) if(s >= sprime[i])         {
               a[cur] = sprime[i];             dfs(i, cur + 1, s - sprime[i]);         } } void solve() {
   int i, j ,k;     num = 0x3f3f3f3f;     dfs(sp, 0, N); if(num == INF)         printf("0\n"); else     {
           printf("%d\n", num);         printf("%d", ans[0]); for(i = 1; i < num; i ++)             printf(" %d", ans[i]);         printf("\n");     } } int main() {
   int i, j, k;     prepare(); while(scanf("%d", &N) == 1)     {
           solve();     } return 0; }

//dp #include
     
       #include
      
        #include
       
         #define MAXD 10010 #define INF 0x3f3f3f3f int N, isprime[MAXD], prime[MAXD], p, sprime[MAXD], sp, a[MAXD], ans[MAXD], num, f[MAXD], fa[MAXD]; int cmp(const void *_p, const void *_q) {
   int *p = (int *)_p; int *q = (int *)_q; return *q - *p; } void prepare() {
   int i, j, k;     memset(isprime, -1, sizeof(isprime));     p = 0; for(i = 2; i <= 10000; i ++) if(isprime[i])         {
               prime[++ p] = i; for(j = i * i; j <= 10000; j += i)                 isprime[j] = 0;         }     sp = 0; for(i = 2; i <= p; i ++) if(isprime[i])             sprime[++ sp] = prime[i];     memset(f, 0x3f, sizeof(f));     f[0] = 0; for(i = 1; i <= 10000; i ++) for(j = 1; j <= sp && sprime[j] <= i; j ++) if(f[i - sprime[j]] + 1 < f[i])             {
                   f[i] = f[i - sprime[j]] + 1;                 fa[i] = i - sprime[j];             } } void solve() {
   int i, j ,k;     num = 0x3f3f3f3f; if(f[N] == INF)         printf("0\n"); else     {
   for(i = N, k = 0; i != 0; i = fa[i])             ans[k ++] = i - fa[i];         qsort(ans, k, sizeof(ans[0]), cmp);         printf("%d\n", k);         printf("%d", ans[0]); for(i = 1; i < k; i ++)             printf(" %d", ans[i]);         printf("\n");     } } int main() {
   int i, j, k;     prepare(); while(scanf("%d", &N) == 1)     {
           solve();     } return 0; }