洛谷P1036 选数【DFS】

题目链接：P1036 选数

代码如下：

#include <iostream> using namespace std; const int N = 60; int a[N], n, k, res[N], cnt; //判断质数 bool prime(int n) { for(int i = 2; i * i <= n; i++) { if(n % i == 0) return false; } return true; } //搜索 void dfs(int u, int start) { if(u == k) { int sum = 0; for(int i = 0; i < k; i++) sum += res[i]; if(prime(sum)) cnt++; return; } //枚举组合数 for(int i = start; i < n; i++) { res[u] = a[i]; dfs(u + 1, i + 1); res[u] = 0; } } int main() { cin>>n>>k; for(int i = 0; i < n; i++) cin>>a[i]; dfs(0, 0); cout<<cnt; return 0; }