P1036 选数

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 int n,k;
 7 int a[30];
 8 int b[30];
 9 bool vis[30];//判重
10 int sum=0;//答案
11 bool judge(long long x)//判断x是否是质数
12 {
13     for(int i=2;i<=sqrt(x);i++)//只用枚举到根号下x（也是一个剪枝）
14     if(x%i==0) return false;//发现一个因数则可跳出，x就一定不是
15     return true;
16 }
17 void dfs(int x,int now,long long ans)//分别表示当前选到了第x位，now一共选了多少数，ans选到现在的和
18 {
19     if(now==k)//已经选够了k个数，即已经有了一种方案
20     {
21         if(judge(ans)) sum++;//判断当前方案是否满足题，可以就将答案加一
22         /*for(int i=0;i<now;i++)
23         printf("%d ",b[i]);
24         printf("\n");*///此处可用于观察每次都选取了那些数
25     } 
26     else
27     {
28         for(int i=1;i<=n;i++)
29         {
30             if(!vis[i]&&i>x)
31             {
32                 vis[i]=true;//标记是否已经选取
33                 //b[now]=a[i]; //此行只适用于检查，方便大家检查每次选那些数是使用，与本题无关
34                 dfs(i,now+1,ans+a[i]);//递归找下一个数
35                 vis[i]=false;//回溯（很重要）！！！！
36             }
37         }
38     }
39 }
40 int main()
41 {
42     scanf("%d%d",&n,&k);
43     for(int i=1;i<=n;i++)
44     scanf("%d",&a[i]);
45     dfs(0,0,0);//解释一下第一个0也就是dfs中的x是用来判重的，这样可以节约时间（因为一组数中选第一第二第三个和
46 //选第一第三第二个其意义是一样的,如1 5 3 2 4中选1 3 2和选1 2 3是一样的）
47     printf("%d",sum);
48     return 0;
49 }
50 //最后，如有不妥，敬请指教。