当前位置：网站首页>【洛谷】P1036 [NOIP2002 普及组] 选数（DFS)

【洛谷】P1036 [NOIP2002 普及组] 选数（DFS)

2022-04-22 15:55:00 【percation】

穿越隧道
在这里插入图片描述

递归组合型的微变型

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int ans;
int n,m;
int res = 0;
int a[N];
bool st[N];
int path[N];
bool is_prime(int x){
    
	for(int i = 2; i <= x/i; i++){
    
		if(x % i == 0) return false;
	}
	return true;
} 
void dfs(int u, int res, int start){
    //u为深度，res为当前所有数的和 ,从当前start开始选，以防重复 
	if(u >= m){
    
// for(int i = 0; i < m; i++){
    
// cout << path[i] <<" ";
// }
// puts("");
		if(is_prime(res)){
    
			ans++;
		}
		return ;
	}
	for(int i = start; i < n; i++){
    
		if(!st[i]){
    
			st[i] = true;
			path[u] = a[i];
			dfs(u + 1, res + a[i],i + 1);
			st[i] = false;
		}
	}
}
int main(){
    
	cin >> n >> m;
	for(int i = 0; i < n; i++){
    
		cin >> a[i];
	}
	dfs(0,0,0);
	cout << ans << endl;
	return 0;
}

版权声明
本文为[percation]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_45866781/article/details/124344740

边栏推荐

猜你喜欢

随机推荐