hdu acm 1051 sticks

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 
 8 int n,falg,a[70],vis[70],ans;
 9 void dfs(int fa,int s,int c)
10 {
11 
12     if(c==1){falg=0;return;}
13     if(fa==0)dfs(ans,0,--c);
14     for(int i=s;i<n;i++)
15     {
16         if(vis[i]||a[i]>fa||!falg) continue;
17         vis[i]=1;
18         dfs(fa-a[i],i+1,c);
19         vis[i]=0;
20         /*******************************************************************/
21         while(a[i]==a[i+1])++i;// 这个剪枝去掉了，相比原来加了100多MS
22         if(fa==a[i]) return;// 这个去掉 +40Ms
23         if(fa==ans)   return;// 这个去掉，TLE。。
24         /*******************************************************************/
25         
26     }
27 }
28 bool cmp(int a,int b)
29 {
30     if(a>b)
31         return true;
32     else
33         return false;
34 }
35 int main()
36 {
37     int sum,c;
38     while(scanf("%d",&n)!=EOF&&n)
39     {
40         sum=0;
41         falg=1;
42         memset(a,0,sizeof(a));
43         for(int i=0;i<n;++i)
44         {
45             scanf("%d",&a[i]);
46             sum+=a[i];
47         }
48         sort(a,a+n,cmp);
49         ans=a[0]-1;
50         while(falg)
51         {
52             ans++;
53             if(sum%ans!=0)continue;
54             c=sum/ans;
55             memset(vis,0,sizeof(vis));
56             dfs(ans,0,c);
57         }
58         printf("%d\n",ans);
59 
60     }
61 }