这是本蒟蒻的第一篇TJ
步骤:
DFS求所有方案
void dfs(int start, int count, int sum) {
if (count == k && ____(1)____) {
ans++;
}
for (int i = start; i <= n; i++) {
dfs(i + 1, count + 1, sum + sz[i]);
}
}
填充空白(1)部分(判断质数)
bool isPrime(int i) {
if (i == 2)
return 1;
for (int j = 2; j * j <= i; j++) {
if (i % j == 0) {
return false;
}
}
return true;
}
两条最有用的代码就在这里! 代码
#include <bits/stdc++.h>
using namespace std;
int ans=0;
int n,k;
int sz[21];
bool isPrime(int i) {
if (i==2) return 1;
for (int j = 2; j*j <= i; j++) {
if (i%j == 0) {
return false;
}
}
return true;
}
void dfs(int start, int count, int sum) {
if (count == k && isPrime(sum)) {
ans++;
}
for (int i = start; i <= n; i++) {
dfs(i + 1, count + 1, sum + sz[i]);
}
}
int main() {
int i;
cin >> n >> k;
for (i = 1; i <= n; i++) {
cin >> sz[i];
}
dfs(1, 0, 0);
cout << ans << endl;
return 0;
}