AcWing 5491. !!!选数——C++ (目前最简题解)
原题链接
简单
本题数据范围比较小,然后就用dfs了,具体的优化期待大佬的分享哦!
#include <iostream>
using namespace std;
const int N = 20;
int q[N];// 定义数组q存储数据
int n, k, res;
bool b[N]; // 定义一个bool类型的数组b, 来判断该数是否选取
// 判断是否是素数
bool su(int p){
if (p < 2) return false;
for (int i = 2; i <= p / i; i ++)
if (p % i == 0) return false;
return true;
}
// 定义一个函数,来讨论每个数的状态,选或不选
void f(int u){
if (u > n){
int sum = 0, t = 0;
for (int i = 1; i <= n; i ++)
if (b[i]) t ++, sum += q[i];
if (t == k && su(sum)) res ++;
return ;
}
b[u] = true;// 选
f(u + 1); // 讨论下一个数的状态
b[u] = false;// 不选(恢复现场)
f(u + 1); // 讨论下一个数的状态
}
int main(){
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i ++) scanf("%d", &q[i]);
f(1);
printf("%d\n", res);
return 0;
}
写得好!
附上另一种
#include[HTML_REMOVED]
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
using namespace std;
typedef long long ll;
const int N = 25;
int arr[N], q[N], n, k;
int res, sum;
bool is_prime(int sum) {
}
void dfs(int x , int start) {
}
main() {
}