洛谷----P1036 [NOIP2002 普及组] 选数

题目描述

已知 nn 个整数 x1,x2,⋯,xn，以及 1 个整数 k（k<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≤n≤20，k<n）。

第二行 n 个整数，分别为 x1,x2,⋯,xn（1≤xi≤5×10^6）。

输出格式

输出一个整数，表示种类数。

输入输出样例

输入 #1复制

4 3
3 7 12 19

输出 #1复制

1

思路：用dfs来做，记录开始选择数字的位置，已经选择了多少位数，现在的和为多少，最后判断一下和是否为质数。

#include <iostream>
#include <math.h>
#include <algorithm>
#include <stack>
#include <string.h>
#include <vector>
#include <cstring>
using namespace std;
int n,k,ans=0;
int a[25];
int fun(int x) {
    for(int j=2; j<=sqrt(x); j++)
        if(x%j==0)
            return 0;
    return 1;
}
void dfs(int s,int nm,int sum) {
    if(s==n) {
        if(nm==k&&fun(sum))
            ans++;
        return;
    }
    dfs(s+1,nm+1,sum+a[s]);
    dfs(s+1,nm,sum);
}
int main() {
    cin>>n>>k;
    for(int i=0; i<n; i++) {
        cin>>a[i];
    }
    dfs(0,0,0);
    cout<<ans<<endl;
    return 0;
}