uestc sticks

转自http://m.blog.csdn.net/blog/wuxinliulei/9052707

Sticks
这一题仍然要采用深度优先搜索+剪枝
这一题的剪枝很重要。
首先题意是要求木棒的最短长度，首先明确一点木棒的长度一定在最长木棒长度---所有木棒长度总和之间
所以在读入木棒长度之后要找出最长的和长度总和两个值。
还有一个理论上分析得出的结果就是长木棒的灵活性较小在拼接的时候要首先拼接长木棒再考虑短木棒
比如要拼接一个长度为8的木棒拼接 5+3 和拼接 5+2+1 其实是等价的但是显然前者对3的利用较好
所以在读入数据之后对木棒的长度进行排序。从大到小。
然后从最大木棒长度就是数组的第一个元素开始进行枚举，
此时又出现一个剪枝就是长度必须是总和的约数这个也是自然的。
下面进行深搜
深搜的结束条件此时也是一个剪枝当已经组合的（木棍长度+1）* 长度之后如果等于总和则 return true 跳出循环得出结果
下面的判断分为三种情况新加上的木棒长度刚好构成一个完整的木棒还有不能构成一个完整的木棒
还有细分出来的起始长度为0无法构成一个完成木棒的情况，这是一个剪枝如果在这种情况下都无法完成的话说明不可能在利用这个
木棒，于是return false 这是为一个一个在for循环里的return false 不然的话都要将for循环进行到底（除非return true）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<iostream>
 6 using namespace std;
 7 #define MAX 64
 8 
 9 
10 int s[MAX], vis[MAX], n, len, sum;
11 
12 
13 bool cmp(int a, int b) 
14 {
15     return a > b;
16 }
17 
18 void input()
19 {
20     int i, j, temp;
21     sum = 0;
22     for (i = 0; i<n; i++)
23     {
24         scanf("%d ", &s[i]);
25         sum += s[i];
26     }
27     sort(s,s+n,cmp);
28 }
29 
30 
31 bool dfs(int now_len, int i, int count)
32 {
33     if ((count + 1)*len == sum)
34     {
35         return true;
36     }
37     for (int k = i; k<n; k++)
38     {
39         if (vis[k]) continue;
40         if (k&&!vis[k - 1] && s[k] == s[k - 1]) continue;
41         if (s[k] + now_len>len) continue;
42         if (now_len + s[k] == len)
43         {
44             vis[k] = 1;
45             bool result = dfs(0, 0, count + 1);
46             vis[k] = 0;
47             return result;
48         }
49         else if (now_len == 0)
50         {
51             vis[k] = 1;
52             bool result = dfs(s[k], k + 1, count);
53             vis[k] = 0;
54             return result;
55 
56 
57         }
58         else if (now_len + s[k]<len)
59         {
60             vis[k] = 1;
61             bool result = dfs(s[k] + now_len, k + 1, count);
62             vis[k] = 0;
63             if (result)
64                 return true;
65         }
66     }
67     return false;
68 }
69 int main()
70 {
71     //freopen("1.txt","r",stdin);
72     while (scanf("%d", &n) == 1 && n != 0)
73     {
74         input();
75         for (len = s[0]; len <= sum; len++)
76         {
77             if (sum%len) continue;
78             memset(vis, 0, sizeof(vis));
79             if (dfs(0, 0, 0))
80                 break;
81         }
82         printf("%d
", len);
83     }
84 }