http://acm.pku.edu.cn/JudgeOnline/problem?id=2362DFS訓練題
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4
5 using namespace std;
6 vector<int> sticks;
7 int mark[25];
8 int s;
9 int dfs(int val,int h,int cnt)
10 {
11 for(int i=h;i<sticks.size();++i){
12 if(mark[i]==0){
13 mark[i]=1;
14 if(val+sticks[i]==s){
15 cnt++;
16 if(cnt==4)return 1;
17 int ans=dfs(0,1,cnt);
18 if(ans==1)return 1;
19 mark[i]=0;
20 return 0;
21 }
22 else if(val+sticks[i]<s){
23 int ans=dfs(val+sticks[i],i,cnt);
24 if(ans==1)return 1;
25 mark[i]=0;
26 }
27 else if(val+sticks[i]>s){
28 mark[i]=0;
29 return 0;
30 }
31 }
32 if(h>0&&mark[0]==0)return 0;
33 }
34 return 0;
35 }
36 int main()
37 {
38 int c;
39 scanf("%d",&c);
40 while(c--){
41 memset(mark,0,sizeof(mark));
42 sticks.clear();
43 int num;
44 int k;
45 scanf("%d",&k);
46 int sum=0;
47 int tmp=0;
48 while(k--){
49 scanf("%d",&num);
50 sticks.push_back(num);
51 sum+=num;
52 if(num>tmp)tmp=num;
53 }
54 if(sum%4!=0||sticks.size()<4){
55 printf("no\n");
56 continue;
57 }
58 s=sum/4;
59 if(s<tmp){
60 printf("no\n");
61 continue;
62 }
63 sort(sticks.begin(),sticks.end());
64 int ans=dfs(0,0,1);
65 if(ans){
66 printf("yes\n");
67 }
68 else printf("no\n");
69 }
70 return 0;
71 }
posted on 2008-07-24 20:56
小果子 閱讀(348)
評論(0) 編輯 收藏 引用