AOJ 1269,PKU 3132 Sum of Different Primes
概要
2数n(<=1120),k(<=14)が与えられる。
nを異なるk種類の素数の和で表すとき、その表し方の個数を求めよ。
ただし順番が異なるだけのものは同じものと見なす。
考え方
メモ化再帰するだけ。
実装(C++)
#include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; vector<int> primes; typedef long long lli; lli dp[1121][15][200]; int solve(int n,int k,int used){ lli res=0; if(n==0&&k==0)return 1; if(k==0)return 0; if(n<=0)return 0; if(dp[n][k][used]>=0)return dp[n][k][used]; for(int i=used;i<(int)primes.size();i++){ if(n-primes[i]<0)break; res+=solve(n-primes[i],k-1,i+1); } return dp[n][k][used]=res; } int main(){ for(int i=2;i<=1120;i++){ bool isprime=true; for(int j=2;j<i;j++)if(i%j==0)isprime=false; if(isprime)primes.push_back(i); } int n,k; memset(dp,-1,sizeof(dp)); for(;;){ cin>>n>>k; if(n==0)break; cout<<solve(n,k,0)<<endl; } return 0; }