[洛谷] P1036选数(DFS入门好题)
题目链接
#include <bits/stdc++.h>
using namespace std;
int ans = 0;
int a[30],n,k;
bool isPrime(long long x)
{
if(x<2) return false;
for(int i=2;i<=x/i;++i)
{
if(x%i==0) return false;
}
return true;
}
int r[30];
void dfs(int x,long long sum,int up) //该选第x个数,和为sum,前一个为up
{
// up:前一个选的是啥
if(n-up+x-1<k) //剪枝
{
return;
}
if(x==k+1)
{
if(isPrime(sum))
{
++ans;
}
return;
}
for(int i=up+1;i<=n;++i)
{
r[x] = i;
dfs(x+1,sum+a[i],i);
}
// dfs(x+1,sum,up);
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;++i)
{
scanf("%d",a+i);
}
ans = 0;
r[0] = 0;
dfs(1,0ll,0);
cout<<ans<<endl;
return 0;
}