0 1背包方案计数问题，坑爹的蓝桥杯，是我理解能力差，还是题意不明白，哎 ，还是没认真读题呀
#include <bits/stdc++.h> using namespace std; #define int long long #define JD(x) setprecision(x) const double PI = acos(-1.0); const int maxn = 1e5 + 5; const int mod = 1e9 + 7; priority_queue<int, vector<int>, greater<int> >q; int dp[maxn]; bool is[maxn]; vector<int>isprime; void f(){ memset(is, true, sizeof is); is[0]=is[1]=false; for(int i=2;i<maxn;i++){ if(is[i]){ if(i>2019)break; isprime.push_back(i); for(int j=i*2;j<maxn;j+=i) is[j]=false; } } } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); f(); //for(int i=0;i<isprime.size();i++)cout<<isprime[i]<<endl; //cout<<isprime.size()<<endl; dp[0]=1; for(int i=0;i<isprime.size();i++){ for(int j=2019;j>=0;j--){ if(j>=isprime[i]){ dp[j]+=dp[j-isprime[i]]; } } } cout<<dp[2019]<<endl; return 0; }
