题解：洛谷 P1036 [NOIP2002 普及组] 选数_p1036 [noip2002 普及组] 选数题解

一道十分标准的dfs。

质数判断

#include <iostream>
#include <cstdio>
using namespace std;
 
int a[30],n,k,ans=0;
 
bool isprime(const int n){
	if(n==1)
		return 0;
	for(int A=2;A<n;A++){
		if(n%A==0)
			return 0;
	}
	return 1;
}
 
void dfs(int A,int m,int he){
	if(A==n){
		if(k==m && isprime(he)){
			ans++;
		}
		return ;
	} 
	dfs(A+1,m,he);
	dfs(A+1,m+1,he+a[A]);
	return ;
}
 
int main(){
	//freopen("num.in","r",stdin);
	//freopen("num.out","w",stdout);
	cin>>n>>k;
	for(int A=0;A<n;A++){
		cin>>a[A];
	}
	dfs(0,0,0);
	cout<<ans;
	return 0;
}