PKU 3132 Sum of Different Primes
http://poj.org/problem?id=3132
二つの数字n,kが与えられる。この時、k個の異なる素数の和でnを表す組み合わせはいくつあるかを求めるというような問題。
ずっとあまり分かっていなかった問題。
素数を1つずつ、使う個数が多いほうから埋めていけば、ダブりがなくいけるようです。
int dp[20][1200]; bool pr[1121]; int npr[1121],pos; main(){ pr[0]=pr[1]=true; for(int i=2;i<1121;i++){ if(pr[i])continue; for(int j=i*2;j<1121;j+=i)pr[j]=true; } rep(i,1121)if(!pr[i])npr[pos++]=i; dp[0][0]=1; rep(p,pos){ for(int k=14;k;k--) for(int i=npr[p];i<1121;i++)dp[k][i]+=dp[k-1][i-npr[p]]; } int n,k; while(cin>>n>>k,n|k)cout<<dp[k][n]<<endl; }