[POJ] 1011 Sticks

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdbool.h>
 4 int i,j,n,m,maxi,sum,ans,
 5     a[100];
 6 
 7 bool vis[100];
 8 
 9 int 
10 pre()
11 {
12     sum=0;ans=0;
13     memset(a,0,sizeof(a));
14     memset(vis,false,sizeof(vis));
15     
16     return 0;
17 }
18 
19 bool 
20 dfs(int num,int pos,int len)
21 {
22     int i;
23     if (num==n) return true;
24     for(i=pos;i<=n;i++)
25     {
26         if(vis[i]) continue;
27         if(a[i]+len<ans)
28         {
29             vis[i]=true;
30             if (dfs(num+1,i+1,len+a[i])) return true;//如果dfs(used+1,i+1,len+a[i])返回false，则第i根不可用，标记为false  
31             vis[i]=false;
32             while((a[i]==a[i+1])&&((i+1)<n))  //长度为a[i]的不能匹配，则和它同样长的不需要再匹配。
33             {
34                 i++;
35             }
36             if (len==0) return false;//如果当前长度为0，证明没有合适的，return false 
37         } else
38         if(a[i]+len==ans)
39         {
40             vis[i]=true;
41             if (dfs(num+1,1,0)) return true;
42             vis[i]=false;
43             return false;
44         }
45     }
46     return false;
47         
48 }
49             
50 void
51 qsort(int head,int tail)
52 {
53     int i,j,x;
54     i=head;j=tail;
55     x=a[head];
56     while(i<j)
57     {
58         while((i<j)&&(a[j]<=x)) j--;
59         a[i]=a[j];
60         while((i<j)&&(a[i]>=x)) i++;
61         a[j]=a[i];
62     }
63     a[i]=x;
64     if (head<(i-1)) qsort(head,i-1);
65     if ((i+1)<tail) qsort(i+1,tail);
66 }
67 
68 int 
69 main()
70 {  
71     
72  while(~scanf("%d\n",&n))
73  {
74      pre();
75      if(n==0) break;
76     for(i=1;i<=n;i++)
77     {
78         scanf("%d",&a[i]);
79         sum+=a[i];
80     }
81      
82    qsort(1,n); //按木棍长度从大到小排序。
83     maxi=a[n];
84     for(i=n;i>=1;i--)
85     {
86         if ((sum%i==0)&&((sum/i)>=maxi))
87         {
88             ans=sum/i;
89             memset(vis,false,sizeof(vis));
90             if (dfs(0,1,0)) 
91             { 
92                 printf("%d\n",ans);
93                 break;
94             }
95         }
96     }
97  }
98     return 0;
99 }