P1832 A+B Problem(再更新)題解
這是本蒟蒻第一次寫題解,請多多指教!
未讀題的請回!本篇不講題意!
解題思路
枚舉i(素數i),用素數判斷函數zhi判讀是否是枚舉的數是否為素數。再用dp存貯個數。切記dp[0]要初始化為1。鄙人尋找許久(約半個小時,其餘題解無此提醒!)。
代碼
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long n,dp[100000001]={0};//完全背包dp數組
bool zhi(int x)//素數篩選
{
for(int i=2;i<x;i++)
if(x%i==0)return false;
return true;
}
int main(void)
{
scanf("%lld",&n);
dp[0]+=1;//切記dp[0]=0
for(int i=2;i<=n;i++)
if(zhi(i))
for(int j=i;j<=n;j++)//dp累加(完全背包正循環)
dp[j]+=dp[j-i];
printf("%lld\n",dp[n]);
return 0;
}