首页 > 代码库 > POJ 3132 Sum of Different Primes DP背包

POJ 3132 Sum of Different Primes DP背包

2024-07-15 18:52:03   221人阅读

http://poj.org/problem?id=3132

题意：

给定n和k，问用恰好k个不同的质数来表示n的方案数。

分析:

n和k都很小。反正就是个背包，选k个物品恰好填满n即可。

 

 1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4  5 bool dp[1200][15]; 6 int ct[1200][15]; 7 int p[1200]; 8 bool a[1200]; 9 int n, k, size;10 void create_prime()11 {12     memset(a, true, sizeof(a));13     size = 0;14     for (int i = 2; i <= 1120; i++){15         if (a[i]) p[size++] = i;16         for (int j = 2*i; j <= 1120; j += i)17             a[j] = false;18     }19 }20 int main()21 {22     create_prime();23     while(scanf("%d%d", &n, &k) && (n + k))24     {25         memset(dp, 0, sizeof(dp));26         dp[0][0] = true;27         ct[0][0] = 1;28         for (int i = 0; i < size; i++){29             int tmp = p[i];30             if (tmp > n) break;31             for (int j = n; j >= tmp; j--)32                 for (int kk = 1; kk <= k; kk++) if (dp[j-tmp][kk-1]){33                     if (!dp[j][kk]){34                         dp[j][kk] = true;35                         ct[j][kk] = ct[j-tmp][kk-1];36                     }37                     else38                         ct[j][kk] += ct[j-tmp][kk-1];39             }40         }41         if (!dp[n][k]) ct[n][k] = 0;42         printf("%d\n", ct[n][k]);43     }44     return 0;45 }

 


联系
我们