1
#include<iostream>
2#include<algorithm>
3#include<memory.h>
4#include<ctime>
5using namespace std;
6int n; //小棒總數(shù)
7int len; //當(dāng)前枚舉的原棒長(zhǎng)度
8int parts; //當(dāng)前組合的原棒數(shù)
9int max; //最長(zhǎng)小棒的長(zhǎng)度
10int sum; //所有小棒的總長(zhǎng)
11int a[100]; //存儲(chǔ)小棒相關(guān)信息
12bool used[100]; //標(biāo)記小棒是否使用
13
14
15bool pt(int a,int b)
16
{return a>b;}
17bool dfs(int res,int cpl,int level)//res:當(dāng)前已組合進(jìn)去的木棒的長(zhǎng)度 cpl:組合進(jìn)去的小木棒的條數(shù)
18{
19
int i;
20 if(res==len)
21
{
22 res = 0;
23 cpl++;
24
}
25 if(cpl == parts)
26 return true;
27 for(i=level;i<n;i++)
28 {
29 if(i && !used[i-1] && a[i]==a[i-1])continue;
30 if(used[i]==0)
31 {
32 if(res + a[i] <len)
33 {
34 used[i] = true;
35 if(dfs(res+a[i],cpl,i+1))return true;
36 used[i] = false;
37 }
38 else if(res+a[i]==len)
39 {
40 used[i] = true;
41 if(dfs(0,cpl+1,0))return true;
42 used[i] = false;
43 }
44 if(res==0) break;
45 }
46
47
48 }
49 return false;
50
}
51int main()
52{
53 int i;
54 int T;
55 cin>>T;
56 while(T--){
57 scanf("%d",&n);
58 sum=0;
59 for(i=0;i<n;i++){
60 scanf("%d",&a[i]);
61 sum+=a[i];
62 used[i]=false;
63 }
64 sort(a,a+n,pt);
65 len=sum/4;
66 parts=4;
67 for(i=0;i<100;i++)
68 used[i]=false;
69 if(sum%4==0&&dfs(0,1,0))
70 {
71 printf("yes\n");
72 }
73 else printf("no\n");
74 }
75 return 0;
76}
77
78
79
posted on 2009-05-14 19:15
yiflying 閱讀(1518)
評(píng)論(0) 編輯 收藏 引用