NOIP2002普及組 選數 choose 解題報告

[問題描述]:

已知 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）。

[輸入]：

鍵盤輸入，格式爲：

n , k （1<=n<=20，k＜n）

x1,x2，…,xn （1<=xi<=5000000）

[輸出]：

格式爲：一個整數（滿足條件的種數）。

[輸入輸出樣例]:

輸入：choose.in

4 3

3 7 12 19

輸出：choose.out

1

【分析】

排列組合問題，直接深度優先搜索（遞歸）即可。 

01 //NOIP2002 Junior
02 #include <iostream>
03 #include <cstdio>
04 #include <cmath>
05 using namespace std;
06 int sum=0;//當前總和
07 int num[21];
08 int n,k;
09 int tot=0;
10
11 bool prime(int num)
12 {
13     if (num==1)return false;
14     for (int i=2;i<=(int)sqrt(double(num));i++)
15         if (num%i==0)
16             return false;
17     return true;   
18 }
19
20
21 void dg(int dep,int loc)
22 {
23     if(k-dep>n-loc) return;
24     if (dep==k+1)
25     {
26         if (prime(sum))
27             tot++;
28     }
29     if (dep<k+1)
30     {
31         for (int i=loc;i<=n;i++)
32         {
33             sum+=num[i];
34             dg(dep+1,i+1);
35             sum-=num[i];
36         }
37     }
38 }
39
40 int main()
41 {
42     freopen("choose.in","r",stdin);
43     freopen("choose.out","w",stdout);
44     cin>>n>>k;
45     for (int i=1;i<=n;i++)
46         cin>>num[i];
47     dg(1,1);
48     cout<<tot<<endl;
49     return 0;
50 }

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	20	0.026 s	275 KB	0
2	正确	20	0.001 s	275 KB	0
3	正确	20	0.001 s	275 KB	0
4	正确	20	0.001 s	275 KB	0
5	正确	20	0.001 s	275 KB	0

运行完成
运行时间 0.028 s
平均内存使用 275 KB
测试点通过状况 AAAAA
得分：100
恭喜你通过了全部测试点!