2019年第十届蓝桥杯（决赛）国赛B组C++（B）

题目： 2019可以被分解成若干个两两不同的素数，请问不同的分解方案有多少种？

注意：分解方案不考虑顺序，如2+2017=2019和2017+2=2019属于同一种方案。

思路先求出2019内的所有素数时间复杂度O(n)（求质素用的欧拉线性筛法，这部分不理解前面有写https://www.jianshu.com/p/ef57c98c0e4e）
再dfs爆索，中间记得剪枝

#include<bits/stdc++.h>
#define mem(kk,int) memset(kk,int,sizeof kk);
using namespace std;
typedef long long ll;

vector<int>prime;//这里写int prime[];也可
bool vis[4000];
ll f[4000][4000];

void init(){//求素数，放入prime里面
    for(int i=2;i<=2019;i++){
        if(!vis[i])prime.push_back(i);
        for(int j=0;i*prime[j]<=2019&&j<prime.size();j++){
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}

ll dfs(ll num,ll sum){
    if(f[num][sum]!=-1)return f[num][sum];
    if(sum==2019)return 1;
    if(num>=prime.size()||sum>2019)return 0;
    ll ans=0;
    ans+=dfs(num+1,sum);//选
    ans+=dfs(num+1,sum+prime[num]);//不选
    return f[num][sum]=ans;
}

int main(){
    init();
    /*for(int i=0;i<prime.size();i++)
        cout<<prime[i]<<" ";
    cout<<endl;*/
    mem(f,-1);
    ll ans=dfs(0,0);
    cout<<ans<<endl;
    return 0;
}