洛谷 P1036 选数

题目传送门

解题思路:

搜索
AC代码:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 
 5 using namespace std;
 6 
 7 int n,k,a[21],ans,num; 
 8 
 9 bool _prime(int x) {
10     if(x == 2) return true;
11     for(int i = 2;i <= sqrt(x); i++) 
12         if(x % i == 0) return false;
13     return true;
14 }
15 
16 inline void dfs(int x,int y) {//选到第x个数,第x-1个数的位置是y 
17     if(x > k) {
18         if(_prime(num)) ans++;
19         return ;
20     }
21     for(int i = y + 1;i <= n; i++) {
22         num += a[i];
23         dfs(x + 1,i);
24         num -= a[i];
25     }
26 }
27 
28 int main()
29 {
30     scanf("%d%d",&n,&k);
31     for(int i = 1;i <= n; i++) 
32         scanf("%d",&a[i]);
33     dfs(1,0);
34     printf("%d",ans);
35     return 0;
36 }