DFS, 33pts 求调!
查看原帖
DFS, 33pts 求调!
246764
Finja_小猴楼主2024/7/10 10:40

在递归的时候用不用考虑这个数字 是选还是不选 ?

#include <bits/stdc++.h>
#include <map>
using namespace std;
//	Finja_xh
//	Allen_9
const int N = 1e8+5;
int data[N];
int n , k;
int ans = 0;
bool K[N];
//map<int , bool> F;
//	cout <<
bool uni (int c)
{
	for(int i = 2; i <= sqrt(c); i ++)
	{
		if(c % i == 0 )
			return false;//合数,不符合要求
	}
	return true;
}
void dfs (int step,int sum,int x)
{
	if(step > n) return ;
	if(x > k) return ;
//	cout << "step = " << step << " sum = " << sum << " x = " << x <<endl;
	 if(x == k)
	{
//			cout << "x = " << x << " k = "<< k <<endl;
		if(K[sum] == 0)
		{
			if (uni(sum))
			{
				ans ++ ;
//				cout << "sum = " << sum <<endl;
				K[sum] = 1;
			}
		}

	}

	for(int i = step ; i <= n ; i++)
	{
		dfs(step + 1 , sum + data[step + 1], x + 1);
		dfs(step + 1 , sum , x);
	}

}

int main()
{

	cin >> n >> k;

	for (int i = 1; i <= n ; i++)
		cin >> data[i];

	dfs(0,0,0);
	cout << ans;

	return 0;
}
2024/7/10 10:40
加载中...