HDOJ1455——DFS + 强剪枝

题意

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.
小明本来有m根长度相同木棍，他把它们胡乱砍成了n段，现在知道每一段的长度，求原来m根木棍有可能的最小长度。

Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output

6
5

问题分析

求m根木棍的最小长度，也就是求m的最大值。
我们从n-1枚举到1，如果n % i == 0，那么这有可能就是一个可行解。我们把可行解放入DFS里搜索，看n根木棍是否可拼成根。这里有很多剪枝技巧，剪枝不当会TLE。这里列举几个比较重要的剪枝。

1. 整除剪枝，如果n%i != 0 ，显然不成立
2. 对于一个新棍子，如果没有一段能拼接上去，那这种情况肯定不成立。因为每一段都必定在某一根棍子上。
3. 在搜索前对棍子用大到小排序，可以有效降低DFS的层数。

代码实现

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 65;
int n,num[maxn],vis[maxn],pre[maxn];
int sum,lim_k,lim_len;
const int cmp(int  &a,int &b){return a > b;}

bool dfs(int k,int len,int pos)
{
  if(k == lim_k)  return true;
  else if(len == lim_len)
  {
    if(dfs(k+1,0,1))  return true;
    else return false;
  }
  if(pos > n) return false;
  for(int i=pos;i<=n;i++)
  {
    if(!vis[i] && len + num[i] <= lim_len)
    {
      vis[i] = 1;
      if(dfs(k,len+ num[i],i+1)) return true;
      vis[i] = 0;
      if(len == 0) return false;  //剪枝2
    }
  }
  return false;
}

bool judge(int k,int length)
{
  memset(vis,0,sizeof(vis));
  lim_k = k;
  lim_len = length;
  if(dfs(0,0,1))  return true;
  else return false;
}

int main()
{
  int maxx,minn,ans;
  while(cin >> n && n)
  {
    sum = maxx = ans = 0;
    minn = 100;
    for(int i=1;i<=n;i++)
    {
      cin >> num[i];
      sum += num[i];
      pre[i] = sum;
      maxx = max(maxx,num[i]);
      minn = min(minn,num[i]);
    }
    sort(num+1,num+1+n,cmp);  //优化3
    if(maxx == minn)
    {
      cout << num[1] << endl;
      continue;
    }
    for(int i=n-1;i>1;i--)
    {
      if(sum % i || sum / i < maxx) continue;  //剪枝1
      if(judge(i,sum / i))  {ans = sum / i; break;};
    }
    cout << (ans == 0 ? sum : ans) << endl;
  }
}