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

本文主要是介绍洛谷题解 - P1036 [NOIP2002 普及组] 选数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

已知 $n$ 个整数 $x_1,x_2,\cdots,x_n$ ，以及 $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$ （ $\le n \le 20$ ， $k < n$ ）。

第二行 $n$ 个整数，分别为 $x_1,x_2,\cdots,x_n$ （ $\le x_i \le 5\times 10^6$ ）。

输出格式

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

样例 #1

样例输入 #1

4 3
3 7 12 19

样例输出 #1

提示

【题目来源】

NOIP 2002 普及组第二题

代码

#include <bits/stdc++.h>
using namespace std;
int n,k,a[25],w[25],cnt;
bool isPrime(int n)
{if(n<=1)return false;if(n==2)return true;for(int i=2; i*i<=n; i++)if(n%i==0)return false;return true;
}
void dfs(int step)
{if(step>n){int sum=0,total=0;for(int i=1; i<=n; i++)if(a[i]==1){sum+=w[i];total++;}if(isPrime(sum) && total==k)cnt++;return;}a[step]=0;dfs(step+1);a[step]=1;dfs(step+1);
}
int main()
{cin>>n>>k;for(int i=1; i<=n; i++)cin>>w[i];dfs(1);cout<<cnt;return 0;
}