首页 > 代码库 > 求方案数的背包。

求方案数的背包。

hdu     2189     悼念512汶川大地震遇难同胞——来生一起走

 题意:    给一个数 n ,求将其拆成由小于n的素数的和的方案数;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        cnt=0;
        Prime(n);
       memset(dp,0,sizeof(dp));        dp[0]=1;       for(int i=0;i<cnt;i++)
        for(int j=0;prime[i]+j<=n;j++)
       {
            dp[j+prime[i]]+=dp[j];
       }
      printf("%d\n",dp[n]);
    }
    return 0;
}


 


求方案数的背包。