题解：P1036 [NOIP 2002 普及组] 选数

· · 题解

solution

一道暴力搜索题。

数据范围小，暴力枚举所有情况，说一下搜索时传的几个参数。设当前选了 x 个数，该从 y 开始选，当前的和是 s。若当前选够 k 个数了，就判断当前的 s 是不是质数，统计答案；若没选够，则继续选。

code

#include<bits/stdc++.h>
using namespace std;
int n, k, a[25], f[25], s, ans;
bool pd(int x){
    if(x<=1)
        return 0;
    for(int i=2; i<=sqrt(x); i++)
        if(x%i==0)
            return 0;
    return 1;
}
void dfs(int x, int y, int s){
    for(int i=y; i<=n; i++)
        if(x==k)
            ans+=pd(s+a[i]);
        else    
            dfs(x+1, i+1, s+a[i]);
}
int main(){
    cin >> n >> k;
    for(int i=1; i<=n; i++)
        cin >> a[i];
    dfs(1, 1, 0);
    cout << ans;
    return 0;
}