赞
踩
已知 n n n 个整数 x 1 , x 2 , ⋯ , x n x_1,x_2,\cdots,x_n x1,x2,⋯,xn,以及 1 1 1 个整数 k k k( k < n k<n k<n)。从 n n n 个整数中任选 k k k 个整数相加,可分别得到一系列的和。例如当 n = 4 n=4 n=4, k = 3 k=3 k=3, 4 4 4 个整数分别为 3 , 7 , 12 , 19 3,7,12,19 3,7,12,19 时,可得全部的组合与它们的和为:
3 + 7 + 12 = 22 3+7+12=22 3+7+12=22
3 + 7 + 19 = 29 3+7+19=29 3+7+19=29
7 + 12 + 19 = 38 7+12+19=38 7+12+19=38
3 + 12 + 19 = 34 3+12+19=34 3+12+19=34
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数: 3 + 7 + 19 = 29 3+7+19=29 3+7+19=29。
第一行两个空格隔开的整数 n , k n,k n,k( 1 ≤ n ≤ 20 1 \le n \le 20 1≤n≤20, k < n k<n k<n)。
第二行 n n n 个整数,分别为 x 1 , x 2 , ⋯ , x n x_1,x_2,\cdots,x_n x1,x2,⋯,xn( 1 ≤ x i ≤ 5 × 1 0 6 1 \le x_i \le 5\times 10^6 1≤xi≤5×106)。
输出一个整数,表示种类数。
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; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。