题目地址:https://vijos.org/p/1128

题目描述

已知 n 个整数 x1,x2,…,xn,以及一个整数 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。

思路

采用DFS遍历的搜索题。

AC代码

/*************************************************************************
    > File Name: 1128.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: Sat 02 May 2015 11:48:19 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

bool isPrime[10000005]; // 素数表
int x[25]; // 读取的数据
int N,K; // 数据的个数N以及K个数的和
int ans = 0; // 符合题意的个数

void DFS(int k, int i, int sum) { // k 当前已加个数, sum为当前和
    if(k == K && isPrime[sum] ) { // 符合题意K个数相加和为素数
        ++ans;
        return;
    }
    for(int j=i; j<N; ++j) { // 开始遍历递归数据
        DFS(k+1, j+1, sum+x[j]);
    }

}
int main()
{
    memset(isPrime, 1, sizeof(isPrime));
    isPrime[1]=0;
    for(int i=2;i<=10000000;++i) // 获取素数表
       if (isPrime[i])
           for(int j=2;i*j<=10000000;++j)
               isPrime[i*j]=0;
    scanf("%d%d", &N, &K);
        for(int i=0; i<N; ++i)
            scanf("%d", x+i);
        DFS(0, 0, 0);
        cout << ans << endl;

    return 0;
}