题目描述
有N根小木棍，他们有各自的长度，若它们能拼成整数多的len长的木棍，求len的最小值。
思路
从题目上看，一个显然的思路是我们可以暴力从小到大枚举len，用dfs看能否拼成这么多木棍。不过裸的dfs肯定T飞了，我们尝试进行优化。
首先从可行性方面进行优化，我们提出五种剪枝：
①一根长木棍用处肯定比用几根短木棍拼成相同长度的作用小，所以我们可以把木棍从大到小排序。
②我们按照这个顺序依次处理每一根木棍，那么显然到第i个木棍时，只能从i+1开始寻找，因为前面的都已用过。
③相同长度的木棍不用搜索多次，可以直接处理。对于找不到时可直接返回。
④判断当前木棍的长度能否拼成len长木棍，不能就直接返回。
⑤找到答案立刻返回。
我们再从最优性方面做出两种剪枝：
⑥设所有木棍长为sum，那我们枚举的len一定能被len整除。
⑦len一定大于等于剩余木棍中最长的。
代码
using namespace std;
int m,n,len,used[70],a[70];
bool f;
bool cmp(int x,int y)
{
return x>y;
}
void dfs(int k,int last,int rest)
{
int i;
if(f)return ; //剪枝⑤
// cout<<k<<' '<<rest<<endl;
if(k==m){f=1;return ;}
if(rest==0)
{
for(i=1;i<=n;i++)
if(!used[i])break ;
used[i]=1;
dfs(k+1,i,len-a[i]);
used[i]=0;
}
for(i=last+1;i<=n;i++) //剪枝②
if(!used[i]&&a[i]<=rest)
{
used[i]=1;
dfs(k,i,rest-a[i]);
used[i]=0;
int j=i;
while(i<n&&a[i]==a[j])i++; //剪枝③
if(i==n)return ;
}
}
int main()
{
int sum=0,minn=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
minn=max(a[i],minn);
// cout<<minn<<endl;
}
sort(a+1,a+n+1,cmp); //剪枝①
/* for(int i=1;i<=n;i++)
printf("%d ",a[i]);
printf("\n");*/
// cout<<sum<<endl;
for(int i=minn;i<=sum;i++) //剪枝⑥
if(sum%i==0) //剪枝⑤
{
// cout<<i<<endl;
memset(used,0,sizeof(used));
f=0;used[1]=1;
len=i;m=sum/i;
dfs(1,1,len-a[1]);
if(f){printf("%d",i);break ;}
}
return 0;
}