zxc10806的部落格

POJ_3132 Sum of Different Primes

團練中我唯一有寫出來的題目 orz....

寫得不是很好 僅供參考用

看到這個直覺就是DP了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#define LI long long int

int checked[1125][15][200] = {};//紀錄有沒有計算過了
LI dp[1125][15][200] ={};//儲存計算過的數字
int p[1125] = {};//prime table
int pm[1125] = {};//store primes
int pn;//number of primes
/*  
* n 是要計算的數字和
* k 是幾個數字
* s 代表從哪一個prime number開始
*/
LI Sum(int n,int k,int s)
{
        int i;
        if(k==1)//
        {
                if(p[n]==0&&pm[s]<=n)//如果是質數而且開始的prime number比n小
                        return 1;
                else return 0;
        }
        if(checked[n][k][s] ==1)//如果紀錄過了就直接回傳
                return dp[n][k][s];
        
        for(i=s;i<pn&&pm[i]<n;i++)
                dp[n][k][s]+=Sum(n-pm[i],k-1,i+1);
        checked[n][k][s] = 1;
        return dp[n][k][s];

} 



using namespace std;

int main(void)
{
        int i,j;
        p[0] = p[1] = 1;
        /*計算質數*/
        for(i=2;i<1125;i++)
        if(p[i]==0)
        {
                pm[pn++] = i;
                for(j=i*i;j<1125;j+=i)
                        p[j] = 1;
        }

        int n;
        
        int k;

        while(~scanf("%d %d",&n,&k))
        {
                if(n==0&&k==0)
                        break;
                
                printf("%lld\n",Sum(n,k,0));

        }


        return 0;
}