【洛谷-递推】P1036 选数

题目描述

已知 $n$ 个整数 $x_1,x_2,\dots ,x_n$，以及$1$个整数$k$(KaTeX parse error: Expected 'EOF', got '&' at position 2: k&?lt;n)。从$n$个整数中任选$k$个整数相加，可分别得到一系列的和。例如当$n=4,k=3$,$4$个整数分别为$3,7,12,19$时，可得全部的组合与它们的和为：
$3+7+12=22$
$3+7+19=29$
$7+12+19=38$
$3+12+19=34$。
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：$3+7+19=29$。

输入输出格式

输入格式

键盘输入，格式为：
$n,k$($1\le n\le 20,k<n$)
$x_1,x_2,\dots ,x_n(1\le x_i\le 5000000)$

输出格式

屏幕输出，格式为：
$1$个整数（满足条件的种数）。

输入输出样例

输入样例 #1

4 3
3 7 12 19

输出样例 #1

1

解题思路

做法分为两个模块，一个遍历从n中取k个数的所有不重复组合，一个将组合的的和判断是否为素数。
其中判断素数的代码很好写，但怎么保证遍历的组合不重复呢?只要确保每次选数都向后选即可。比如第一个数从第1~n个数中选，如果我选了a，那么第二个数就从a~n中选。以此类推。而用深搜可以保证每个组合都被遍历到。

完整代码

#include<iostream>
#include<cmath>using namespace std;int n, k,sum;
int arr[25];bool isPrime(int num) {
    int maxi = sqrt(num);for (int i = 2; i <= maxi; i++) {
    if (num % i == 0)return false;}return true;
}
//当前下标，总和，添加数量
void dfs(int idx, int total,int kt) {
    if (kt == k) {
    if (isPrime(total))sum++;}else if (idx == n)return;else {
    for (int i = idx + 1; i < n; i++)dfs(i, total + arr[i], kt+1);}
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> k;for (int i = 0; i < n; i++)cin >> arr[i];dfs(-1, 0, 0);cout << sum;return 0;
}