蓝桥杯|2019第十届蓝桥杯B组决赛题解第二题

求两两不同的素数组成2019的方案数
注意点:并不是两个不同的素数,再者直接搜索应该会TimeLimited,所以用dp或者记忆化搜索,方案数可能很多,记得用long long
结果: 55965365465060
代码:

#include #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int maxn = 3e5+55555; const ll mod = 998244353; const double eps = 1e-7; bool vis[12345]; vectorprime; ll f[3000][3000]; void init() { //素数筛 for(int i = 2; i<= 3000; i++) { if(!vis[i]) { for(int j = i*i; j<= 3000; j+= i) { vis[j] = true; } } } for(int i = 2; i<= 2019; i++) { if(!vis[i]) prime.push_back(i); } }ll dfs(int pos,int sum) { if(f[pos][sum]!= -1) return f[pos][sum]; if(sum == 2019) return 1; if(pos>= prime.size()||sum> 2019) return 0; ll ans = 0; ans+= dfs(pos+1,sum); // 不要当前这个素数 ans+= dfs(pos+1,sum+prime[pos]); // 要当前这个素数 return f[pos][sum] = ans; }int main() { init(); mem(f,-1); ll ans = dfs(0,0); cout<

【蓝桥杯|2019第十届蓝桥杯B组决赛题解第二题】

    推荐阅读