洛谷 P1036 选数

嗯....

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

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

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

 

先看一下题目:

 

题目描述

已知 n 个整数 x1,x2,…,xn,以及1个整数k(k<n)。从n个整数中任选k个整数相加,可分别得到一系列的和。例如当n=4,k=3n=4,k=3n=4,k=3,444个整数分别为3,7,12,19时,可得全部的组合与它们的和为:

3+7+12=22

3+7+19=29

7+12+19=38

3+12+19=34

现在,要求你计算出和为素数共有多少种。

例如上例,只有一种的和为素数:3+7+19=29。

输入输出格式

输入格式:

键盘输入,格式为:

n,k(1≤n≤20,k<n)

x1,x2,…,xn(1≤xi≤5000000)

输出格式:

屏幕输出,格式为: 1个整数(满足条件的种数)。

输入输出样例

输入样例#1: 
4 3
3 7 12 19
输出样例#1: 
1


一道比较典型的深搜...

思路:

在n个数和每k个数这两个范围中进行搜索,然后看加起来的和是否为素数即可(详细的也不会说...注意边界条件为n个数全搜完和已经搜完k个数判断后...

大体过程:
主函数输入输出调用----->is_prime函数判断是否为素数------->深搜

下面是AC代码:
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 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 }

 

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

上一篇:BZOJ p1036 树的统计(树链剖分)


下一篇:解决了一个小问题——读源码真的只是为了应付面试?