题目大意：有一堆木棍 由几个相同长的木棍截出来的，求那几个相同长的木棍最短能有多短？
深搜+剪枝 具体看代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
using namespace std;
int N,M;
int A[100],Max=-1,Sum,NN;
int visit[100];
bool cmp(int a,int b)
{
return a>b;
}
void input()
{
memset(visit,0,sizeof(visit));
Max=-1;Sum=0;
for(int i=1;i<=N;i++)
{
scanf("%d",&A[i]);
if(A[i]>Max) Max=A[i];
Sum+=A[i];
}
}
int dfs(int now,int nown,int pos)
{
int ok=0;
if(nown==NN) return 1;
for(int i=pos+1;i<=N;i++)
{
if(visit[i]==0)
{
if(now+A[i]<=M)
{
visit[i]=1;
if(now+A[i]==M) ok=dfs(0,nown+1,0);
else ok=dfs(now+A[i],nown,i); //剪枝1 次要剪枝
visit[i]=0;
if(ok) return 1;
if(now==0) return 0; //剪枝2 必须剪枝 now==0 表示这是一个新的一根但i却依旧不能加进去
// 在新的一根中都不能满足，说明未来所有的木棍中都没有他的容身之所，直接return 0；本题精华所在
while(A[i]==A[i+1]) i++; //剪枝3 次要剪枝 如果这个不满足的话，与他相同的也不可能满足这根
}
}
}
return 0;
}
void solve()
{
sort(A+1,A+N+1,cmp);
for(int i=Max;i<=Sum;i++)
{
if(Sum%i==0)
{
memset(visit,0,sizeof(visit));
M=i;
NN=Sum/i;
if(dfs(0,0,0)) {
printf("%d
",M);
break;
}
}
}
}
void init()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
int main()
{
// init();
while(cin>>N&&N!=0)
{
input();
solve();
}
}