题解：B4141 [信息与未来 2016] 素数分解

· · 题解

题解

题目给我们的任务是求一个正整数最多能分解成多少不同质数的和，首先想到暴力，but数据范围是10≤n≤200，因此， O(2^n) 的时间复杂度是不可通过的，但只需要用dfs搜索+简单的剪枝就可AC，详细操作可看代码注释

code:

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int prime[50]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199};
int uu=1;
// bool is_prime(int n){
//     if(n<2)return 0;
//     if(n==2)return 1;
//     for(int i=2;i<=n;i++){
//         if(n%i==0)return 0;
//     }
//     return 1;
// }
// void primenumber(){//也不知道为啥，一用这函数就超时，只能打表
//     for(int i=1;i<=200;i++){
//         if(is_prime(i)){
//             prime[uu++]=i;
//         }
//     }
// }
void dfs(int x,int y,int cnt){//dfs(x,y,cnt)，x表示选到了第几个数，y表示数字和，cnt表示选的数的数量
    if(x>46||y>n)return;//dfs的出局条件，考虑过最后一个数了和数字和超过n
    if(y==n){//数字和等于n
        ans=max(cnt,ans);//选最大
        return;
    }
    dfs(x+1,y,cnt);//抛弃下一个数
    dfs(x+1,y+prime[x+1],cnt+1);//选下一个数
}
int main(){
    cin>>n;
    //primenumber();
    dfs(0,0,0);//开始遍历
    cout<<ans;
    return 0;//养成好习惯
}