vijos 1128 N个数选K个数 (DFS )

从 n 个整数中任选 k 个整数相加，可分别得到一系列的和要求你计算出和为素数共有多少种

IN
4 3
3 7 12 19

OUT
1

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cmath>
 4 using namespace std ;
 5 
 6 int a[22] ;
 7 int ans = 0 ;
 8 int n , k ;
 9 
10 bool isp (int val )  
11 {
12      int i ;
13      if (val == 1)
14        return 0 ;
15      for (i = 2 ; i <= sqrt(val) ; i++)
16      {     
17          if (val % i == 0)
18              return 0 ;
19      }
20      return 1 ;
21 
22 }
23 
24 void dfs(int cur , int cnt , int num)
25 {
26     if (cnt == k)
27     {
28         if (isp(num))
29            ans++ ;
30         return ;
31     }
32     int i ;
33     for (i = cur ; i <= n ; i++)
34        dfs(i+1 , cnt+1 , num+a[i]) ;
35 }
36 
37 int main ()
38 {
39 
40     while (scanf("%d %d" ,&n , &k) != EOF)
41     {
42         ans = 0 ;
43         int i ;
44         for (i = 1 ; i <= n ; i++)
45             scanf("%d" , &a[i]) ;
46         dfs(1 , 0 , 0) ;
47         printf("%d
" , ans) ;
48     }
49     
50     
51     return 0 ;
52 }

View Code