Poj1011 Sticks(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.输入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.输出The output should contains the smallest possible length of original sticks, one per line.样例输入

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

样例输出

6
5

题意：给出若干个木棒的长度，要求将这些木棒拼成尽可能多的长度相同的木棒。（保证输入合法）

题解：

• 容易想到的是，我们可以从小到大枚举原始木棒的长度len，且len是总长sum的约数。
• 对于每个len，我们搜索所面临的状态包括：已经拼好的原始木棒根数、正在拼的原始木棒的当前长度，每个木棍的使用情况。
• 我们每次从尚未使用的木棒中选择一根，拼入。
• 递归边界就是拼好或者失败。
• 这个算法的效率过低，我们依次考虑几类剪枝。
  1. 优化搜索顺序
     1. 将木棍从大到小拼入
  2. 排除等效冗余：对于一根正在拼的木棒
     1. 可以限制先后加入的木棍的长度递减。
     2. 不加入与最近一次失配木棒长度相同的木棒。
     3. 尝试放入第一根就递归失败，那么直接GG。
     4. 拼好这跟后递归失败，GG。（是不是和上一条有点重？）

• //#include<bits/stdc++.h>
  #include<algorithm>
  #include <iostream>
  #include  <fstream>
  #include  <cstdlib>
  #include  <cstring>
  #include  <cassert>
  #include   <cstdio>
  #include   <vector>
  #include   <string>
  #include    <cmath>
  #include    <queue>
  #include    <stack>
  #include      <set>
  #include      <map>
  using namespace std;
  #define P(a,b,c) make_pair(a,make_pair(b,c))
  #define rep(i,a,n) for (int i=a;i<=n;i++)
  #define per(i,a,n) for (int i=n;i>=a;i--)
  #define CLR(vis) memset(vis,0,sizeof(vis))
  #define MST(vis,pos) memset(vis,pos,sizeof(vis))
  #define pb push_back
  #define mp make_pair
  #define all(x) (x).begin(),(x).end()
  #define fi first
  #define se second
  #define SZ(x) ((int)(x).size())
  typedef pair<int,pair<int,int> >pii;
  typedef long long ll;
  typedef unsigned long long ull;
  const ll mod = 1000000007;
  const int INF = 0x3f3f3f3f;
  ll gcd(ll a, ll b) {
  	return b ? gcd(b, a%b) : a;
  }
  template<class T>inline void gmax(T &A, T B){
      (A<B)&&(A=B);//if(B>A)A=B;
  }
  template<class T>inline void gmin(T &A, T B){
      (A>B)&&(A=B);//if(B<A)A=B;
  }
  template <class T>
  inline bool scan_d(T &ret) {
  	char c;
  	int sgn;
  	if(c=getchar(),c==EOF) return 0; //EOF
  	while(c!='?'&&(c<'0'||c>'9')) c=getchar();
  	sgn=(c=='?')?-1:1;
  	ret=(c=='?')?0:(c-'0');
  	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
  	ret*=sgn;
  	return 1;
  }
  inline void outt(int x) {
  	if(x>9) outt(x/10);
  	putchar(x%10+'0');
  }
  const int MAXN = 1e5+10; 
  int a[100],vis[100],n,len,cnt;
  bool dfs(int num,int cap,int last){
  	if(num>cnt)return true;
  	if(cap==len)return dfs(num+1,0,1);
  //	int f=0;
  	rep(i,last,n){
  		if(!vis[i]&&(cap+a[i]<=len)){ //f!=a[i]
  			vis[i]=1;
  			if(dfs(num,cap+a[i],i+1))return true;
  //			fail=a[i];
  			vis[i]=0;
  			if(cap==0||cap+a[i]==len)return false;
  		}
  	}
  	return false;
  }
  bool cmp(int a,int b){
  	return a>b;
  }
  int main(){
  	while(~scanf("%d", &n)&&n){
  		int sum=0,maxx=0;
  		rep(i,1,n)scan_d(a[i]),sum+=a[i],gmax(maxx,a[i]);
  		sort(a+1,a+n+1,cmp);
  		rep(i,maxx,sum){
  			if(sum%i)continue;
  			cnt=sum/i;
  			len=i;
  			CLR(vis);
  			if(dfs(1,0,1))break;		
  		}
  		cout<<len<<endl;
  	}
  	return 0;
  }