P1036选数
-
链接
-
思路
DFS
-
代码实现
#include<bits/stdc++.h> using namespace std; const int maxn = 25; typedef long long ll; ll a[maxn]; ll n,k; ll ans; bool check(ll x){ for(int i = 2; i*i <= x; i++){ if(x%i==0) return 0; } return 1; } void dfs(int x,ll y, int cnt){ if(cnt==k){ if(check(y)) //如果满足条件就让答案+1 ans++; return ; } if(x>n) return ;//x>n表示前n个数都遍历完了,不能继续遍历 dfs(x+1,y,cnt);//不选x,状态发生变化,进入下一层遍历 dfs(x+1,y+a[x],cnt+1); //选x,进入下一层遍历 return ; } int main(void){ cin >> n >> k; for(int i = 1; i <= n; i++){ cin >> a[i]; } dfs(1,0,0); cout<<ans<<endl; return 0; }