题目链接
洛谷 P1832 A+B Problem（再升级）
思路分析
这题同前几题一样，物体的重量与价值相同，只是需要我们自己寻找物品。由于问的是拆分成若干质数的和，所以应为完全背包求方案数，物品即为小于 \(n\) 的所有质数，遍历枚举即可。时间复杂度 \(O(n^2\sqrt{n})\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int N=1e3+10;
int n;
ll dp[N];bool isPrime(int x){for (int i=2;i*i<=x;++i){if (x%i==0) return 0;}return 1;
}
int main(){scanf("%d",&n);dp[0]=1;for (int i=2;i<=n;++i){if (isPrime(i)){for (int j=i;j<=n;++j) dp[j]+=dp[j-i];}}printf("%lld",dp[n]);return 0;
}