P1036选数

P1036选数

  1. 链接

    P1036 选数

  2. 思路

    DFS

  3. 代码实现

    #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;
    } 
上一篇:P1036 选数(DFS+不降原则去重)


下一篇:solarwinds之配置系统管理(System manager)