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个素数

注意递推的顺序是倒着推的,否则会计算重复的情况。

代码中第二重和第三重循环的顺序可互换。

 #include <cstdio>
#include <cmath> const int maxp = ;
const int maxn = ;
int cnt = ;
int prime[maxp];
bool vis[maxn + ]; int d[][maxn + ]; void Init()
{
int m = sqrt(maxn + 0.5);
for(int i = ; i <= m; ++i) if(!vis[i])
for(int j = i * i; j <= maxn; j += i) vis[j] = true;
for(int i = ; i <= maxn; ++i) if(!vis[i]) prime[cnt++] = i;
} void dp()
{
d[][] = ;
for(int i = ; i < cnt; ++i)
for(int j = ; j > ; --j) //j个质数的和
for(int k = maxn; k >= prime[i]; --k) //为k
d[j][k] += d[j-][k-prime[i]];
} int main()
{
//freopen("in.txt", "r", stdin);
Init();
dp();
int k, n;
while(scanf("%d%d", &n, &k) == && n) printf("%d\n", d[k][n]); return ;
}

代码君

上一篇:分布式服务框架Dubbo入门案例和项目源码


下一篇:Codeforces Round #214 (Div. 2) C. Dima and Salad (背包变形)