首页 > 代码库 > [UVa1213]Sum of Different Primes（递推，01背包）

[UVa1213]Sum of Different Primes（递推，01背包）

2024-08-22 22:30:47   220人阅读

题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3654

题意：把n拆成k个不同素数的和，有多少种拆法。

dp(i,j)表示数字为i时，有j个不同素数和的组合数。

先枚举素数的上界k，注意是不同素数，那就再在k个素数中做01背包，dp(i,j)+=dp(i-p,j-1)统计出现次数就行了。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const int maxn = 1320;
 6 bool isprime[maxn];
 7 int prime[maxn];
 8 int pcnt;
 9 int n, k;
10 LL dp[maxn][maxn];
11 
12 void init() {
13   memset(isprime, true, sizeof(isprime));
14   memset(prime, 0, sizeof(prime));
15   pcnt = 0;
16 }
17 void getPrime() {
18     init();
19   prime[0] = prime[1] = 0;
20   for(int i = 2; i <= maxn; i++) {
21     if(isprime[i]) prime[++pcnt] = i;
22     for(int j = 1; j <= pcnt; j++) {
23           if(i * prime[j] > maxn) break;
24         isprime[i*prime[j]] = 0;
25         if(i % prime[j] == 0) break;
26     }
27   }
28 }
29 
30 int main() {
31     // freopen("in", "r", stdin);
32     // freopen("out", "w", stdout);
33     getPrime();
34     memset(dp, 0, sizeof(dp));
35     dp[0][0] = 1;
36     for(int k = 0; k < pcnt; k++) {
37         for(int i = 1120; i >= 0; i--) {
38             int bound = lower_bound(prime, prime+k, i) - prime + 1;
39             for(int j = 1; j < bound; j++) {
40                 int& p = prime[k];
41                 if(p > i) break;
42                 dp[i][j] += dp[i-p][j-1];
43             }
44         }
45     }
46     while(~scanf("%d%d",&n,&k) && n+k) {
47         printf("%lld\n", dp[n][k]);
48     }
49     return 0;
50 }

 

[UVa1213]Sum of Different Primes（递推，01背包）


联系
我们