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

PCSJZ · 2025-02-25 12:25:35 · 题解

思路

考虑 dfs，2 个参数，一个是当前到第几位了，还有一个是从哪里开始，每次进入递归前，加上这个数，跳出递归后减掉这个数。最后判断是不是素数。

代码

#include<iostream>
#include <cmath>
#include <cstdio>
#define MAXN 25
using namespace std;
int n, k, num[MAXN], visit[1001];
int cnt, ans;
bool ss(int n) {
    if(n == 1) return 0;
    if(n == 2) return 1;
    for(int i = 2; i <= sqrt(n); i++)
        if(n % i == 0) return 0;
    return 1;
}
void DFS(int start, int end) {
    if(start > k) {
        if(ss(cnt)) ans++;
        return ;
    }
    else {
        for(int i = end + 1; i <= n; i++) {
            cnt += num[i];
            DFS(start + 1, i);
            cnt -= num[i];
        }
    }
}
int main() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> num[i];
    DFS(1,0);
    cout << ans << endl;
    return 0;
}