首页 > 代码库 > UVa 1213 (01背包变形) Sum of Different Primes
UVa 1213 (01背包变形) Sum of Different Primes
题意：
选择K个质数使它们的和为N，求总的方案数。
分析：
虽然知道推出来了转移方程， 但还是没把代码敲出来，可能基本功还是不够吧。
d(i, j)表示i个素数的和为j的方案数，则 d(i, j) = sigma d(i-1, j-p[k]) ，其中p[k]表示第k个素数
注意递推的顺序是倒着推的，否则会计算重复的情况。
代码中第二重和第三重循环的顺序可互换。
1 #include <cstdio> 2 #include <cmath> 3 4 const int maxp = 190; 5 const int maxn = 1120; 6 int cnt = 0; 7 int prime[maxp]; 8 bool vis[maxn + 10]; 9 10 int d[15][maxn + 10];11 12 void Init()13 {14 int m = sqrt(maxn + 0.5);15 for(int i = 2; i <= m; ++i) if(!vis[i])16 for(int j = i * i; j <= maxn; j += i) vis[j] = true;17 for(int i = 2; i <= maxn; ++i) if(!vis[i]) prime[cnt++] = i;18 }19 20 void dp()21 {22 d[0][0] = 1;23 for(int i = 0; i < cnt; ++i)24 for(int j = 14; j > 0; --j) //j个质数的和25 for(int k = maxn; k >= prime[i]; --k) //为k26 d[j][k] += d[j-1][k-prime[i]];27 }28 29 int main()30 {31 //freopen("in.txt", "r", stdin);32 Init();33 dp();34 int k, n;35 while(scanf("%d%d", &n, &k) == 2 && n) printf("%d\n", d[k][n]);36 37 return 0;38 }
UVa 1213 (01背包变形) Sum of Different Primes
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。