POJ 1011 Sticks（dfs+剪枝）

http://poj.org/problem?id=1011

题意：若干个相同长度的棍子被剪成若干长度的小棍，求每根棍子原来的可能最小长度。

思路：很经典的搜索题。

我一开始各种超时，这题需要很多剪枝。

 1 #include<iostream>
 2 #include<string>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int n;
 8 int a[70];
 9 int vis[70];
10 
11 bool cmp(int a, int b)
12 {
13     return a > b;
14 }
15 
16 int dfs(int len, int left_len, int number) //棍子长度、还需要匹配长度、未匹配棍子数量
17 {
18     if (left_len == 0 && number == 0)  return len;   //所有棍子已全部匹配完毕
19     if (left_len == 0)  //已匹配完一根棍子
20         left_len = len;
21     for (int i = 0; i < n; i++)
22     {
23         if (!vis[i] && a[i] <= left_len)
24         {
25             vis[i] = 1;
26             if (dfs(len, left_len - a[i], number - 1))  //深搜
27                 return len;
28             vis[i] = 0;
29             if (left_len == a[i] || len == left_len)  break; //剪枝，没有数可以和当前值匹配，直接跳出循环
30             while (a[i] == a[i + 1]) i++;  //剪枝，如果后面和前面一样，则跳过
31         }
32     }
33     return 0;
34 }
35 
36 int main()
37 {
38     //freopen("D:\txt.txt", "r", stdin);
39     while (cin >> n && n)
40     {
41         memset(vis, 0, sizeof(vis));
42         int sum = 0;
43         int maxn = 0;
44         for (int i = 0; i < n; i++)
45         {
46             cin >> a[i];
47             sum += a[i];
48             //if (a[i]> maxn)  maxn = a[i]; //记录长棍子，dfs时从最长棍子开始
49         }
50         int k = 0;
51         sort(a, a + n,cmp);
52         for (int i = a[0]; i <= sum; i++)
53         {
54             if (sum%i == 0)  //剪枝，不能除尽说明棍子长度不能为i
55             {
56                 k = dfs(i, 0, n);
57                 if (k) break;
58             }
59         }
60         cout << k << endl;
61     }
62     return 0;
63 }