POJ 1011 -- Sticks

POJ 1011 -- Sticks
 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxm = 64+6;
 6 int sum;///正方形的周长
 7 int m;///小木棍的根数
 8 int stick[maxm];///记录小木棍长度的数组
 9 bool visit[maxm];
10 int side;
11 bool dfs(int num,int len,int s)  //num:已组合的正方形的边数  len:当前组合的边已组合的长度,len<=side
12 {                                                      //s:stick[]的搜索起点
13     if(num==sum/side-1)   //剪枝
14         return true;
15 
16     for(int i=s;i<m;i++)
17     {
18         if(visit[i])
19             continue;
20 
21         visit[i]=true;
22         if(len+stick[i]<side)
23         {
24             if(dfs(num,len+stick[i],i))  //继续构建当前side
25                 return true;
26         }
27         else if(len+stick[i]==side)
28         {
29             if(dfs(num+1,0,0))  //构建新side
30                 return true;
31         }
32         visit[i]=false;
33         if(len==0)  //剪枝，构建新棒时，对于新棒的第一根棒子，在搜索完所有棒子后都无法组合
34             break;  //则说明该棒子无法在当前组合方式下组合，不用往下搜索(往下搜索会令该棒子被舍弃)，直接返回上一层
35     }
36 
37     return false;
38 }
39 
40 int main()
41 {
42     int n;///测试样例个数
43     while(cin>>m && m)
44     {
45         sum = 0;
46         int longest=0;
47         memset(visit,false,sizeof(visit));
48         for(int i=0;i<m;i++)
49         {
50             cin>>stick[i];
51             if(stick[i]>longest)
52                 longest = stick[i];
53             sum += stick[i];
54         }
55         sort(stick,stick+m);
56         for(int k=longest;k<=sum;k++)
57         {
58             if(sum%k) continue;
59             side = k;
60             if(dfs(0,0,0))
61             {
62                 cout<<k<<endl;
63                 break;
64             }
65         }
66     }
67     return 0;
68 }