hdu1455Sticks(经典dfs+剪枝)

Sticks

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13807 Accepted Submission(s): 4270

Problem Description

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

Input

The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.

Output

The output file contains the smallest possible length of original sticks, one per line.

Sample Input

5 2 1 5 2 1 5 2 1

1 2 3 4

Sample Output

我做的第二道dfs题。。。

题意：给出n个小木棒的长度，他们是又数根长度相同的木棒剪短得来的，问没剪短之前的木棒长度最短是多少

题解：要把这些小木棒拼接成数根长度相同的长木棒。要用到搜索算法。但因为搜索算法时间复杂度较高，需要剪枝才行。可以先给小木棒从大到小排个序，最后拼成的长木棒长度肯定在小木棒长度最大值和所有小木棒加起来的长度之间（因为是拼起来的，不可能比原来小木棒还短）。然后判断小木棒长度总和与假设的长木棒原长是不是整除关系。是的话就按照这个假设长度搜索，看不能全部拼成。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 70;
 4 const int INF = 0x3f3f3f3f;
 5 int n, sumv, target, aim;//target表示目标的棍子个数，aim表示目标的棍子长度,sumv为所有木棍总长度 
 6 int stick[maxn], vis[maxn];//vis数组标记 ，stick存储输入的木棒长度 
 7 bool cmp(int a, int b) {
 8     return a > b;
 9 }
10 bool dfs(int cnt, int len, int pos) {
11     if(cnt == target) return true;//根数对上就返回 退出dfs
12     if(len == aim) return dfs(cnt+1, 0, 0); //当拼完一根后，继续拼下一根
13     for(int i = pos; i < n; i++) {//从大到小排序后，按顺序搜索
14         if(!vis[i] && len+stick[i] <= aim) {
15             vis[i] = 1;
16             if(dfs(cnt, len+stick[i], i+1)) return true;
17             vis[i] = 0;                         //只有失败才会运行到下面，否则是直接返回的
18             if(len == 0) return false;                     //如果第一根时失败  剪枝
19             while(i+1 < n && stick[i+1] == stick[i]) i++;  //如果下一根长度跟当前的失败的长度一样，剪枝
20         }
21     }
22     return false;
23 }
24 int main() {
25     while(~scanf("%d", &n), n) {
26         sumv = 0;
27         for(int i = 0; i < n; i++) {
28             scanf("%d",&stick[i]);
29             sumv += stick[i];
30         }
31         sort(stick, stick+n, cmp);
32         int ans = 0;
33         for(int i = stick[0]; i <= sumv; i++) {//拼好后的木棒长度只会在stick[0]和总长度之间 
34             if(sumv % i == 0) {
35                 memset(vis, 0, sizeof(vis));
36                 aim = i;
37                 target = sumv / aim;
38                 if(dfs(0, 0, 0)) {
39                     ans = aim;
40                     break;
41                 }
42             }
43         }
44         printf("%d
",ans);
45     }
46     return 0;
47 }