社区讨论

求各位大佬帮忙看一下哪里错了

P1036[NOIP 2002 普及组] 选数参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@locfaigq
此快照首次捕获于
2023/10/30 12:51
2 年前
此快照最后确认于
2023/11/05 00:28
2 年前
查看原帖
基本的思路就是DFS
CPP
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 30;

int n, k, ans = 0, sum = 0;
int a[N], path[N];
bool st[N];

bool isPrime(int num)
{
	if(num < 2) return false;
	for(int i = 2; i<=num/ i; i++)
	{
		if(num % i == 0)
		{
			return false; 
		}
	}
	
	return true;
 } 


void dfs(int u)  //u代表枚举到了第几个数
{
	if(u >= k + 1)
	{
		//for(int i = 1; i<=k; i++) printf("%d ", path[i]);
		//puts("");
		
		for(int i = 1; i<=k; i++) sum += path[i];
		
		if(isPrime(sum)) ans++;
		//ans++;
		return;
	}
	
	for(int i = 1; i<=n; i++)
	{
		if(!st[i] && path[u - 1] <= a[i])
		{
			sum += a[i];
			st[i] = true;
			path[u] = a[i];
			dfs(u + 1);
			
			//恢复现场
			st[i] = false; 
		}
	}
}


int main()
{
	cin>>n>>k;
	for(int i = 1; i<=n; i++)
	{
		cin>>a[i];
	}
	
	dfs(1);
	
	cout<<ans<<endl;
	
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...