嗯....

这种类型的题在新手村出现还是比较正常的，

但是不知道为什么它的分类竟然是过程函数与递归！！！（难道这不是一个深搜题吗？？？

好吧这就是一道深搜题，所以千万别被误导...

 

先看一下题目：

一道比较典型的深搜... 思路： 在n个数和每k个数这两个范围中进行搜索，然后看加起来的和是否为素数即可（详细的也不会说...注意边界条件为n个数全搜完和已经搜完k个数判断后... 大体过程： 主函数输入输出调用----->is_prime函数判断是否为素数------->深搜 下面是AC代码：

1 #include
        
          2 #include
         
           3 #include
          
            4  5 using namespace std; 6  7 int x[5000005], n, k, total; 8 inline bool is_prime(int x){ 9     for(int i = 2; i <= sqrt(x); i++)10         if(x % i == 0) return false;11     return true;12 } //筛素数 13 14 inline void dfs(int step, int sum, int cnt){15     if(step == n + 1 || cnt == k){ // 如果已经进行到了n+1次或者是已经有k个数， 16         if(is_prime(sum) && cnt == k)//判断选k个数后的和是否为素数 17             total++; // 方案+1 18         return;19     }20     dfs(step+1, sum + x[step], cnt+1);//继续搜索，选择下一个数 21     dfs(step+1, sum, cnt);//继续枚举不选择下一个数的情况 22     return;23 }//深搜 24 int main(){25     scanf("%d%d", &n, &k);26     for(int i = 1; i <= n; i++){27         scanf("%d", &x[i]);28     }29     dfs(1, 0, 0);30     printf("%d", total);31     return 0;32 }
          
         
        

 

嗯... 关于深搜就是这样 ...