[洛谷] P1036选数(DFS入门好题) Apare_xzc

[洛谷] 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;
}

全部评论

相关推荐

缒梦&独舞:这家公司是这样的,去年给我实习offer了,不过也是面着玩儿的,他周六还要去做公益志愿活动
点赞 评论 收藏
分享
05-12 17:28
已编辑
门头沟学院 硬件开发
ldf李鑫:不说公司名祝你以后天天遇到这样的公司
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务