传送门！
题目分析
首先分析可原来的小木棍的最小的长度应该在 Lmax-∑L（这是显然的啊） 那么我们把小木棍长度降序排列，便于剪枝和操作 从小到大枚举长度，len需要满足∑L%len==0（这也是显然啊） DFS中有三个参数 x表示当前要拼成长度为len的大木棍剩余的长度 next表示上一个枚举木棍的位置，因为从大到小排序了，下一个枚举的木棍应该比当前的木棍小 num表示已经拼成的长度为len的大木棍的数量
剪枝
如果当前木棍拼失败的话，并且这个木棍的长度正好为剩余的长度x，那么直接跳出循环 如果当前木棍拼失败的话，并且这个剩余的长度x为len，那么直接跳出循环 如果当前木棍拼失败的话，那么跟此木棍长度相同的木棍一定不成功，直接跳过它们
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int a[
100];
int ans,sum;
bool f[
100];
int n;
bool comp(
int a,
int b)
{
return a>b;
}
bool dfs(
int x,
int net,
int num,
int len)
{
if(num==sum)
{
ans=len;
return 1;
}
if(x==
0)
if(dfs(len,
1,num+
1,len))
return 1;
for(
int i=net;i<=n;i++)
if(!f[i]&&a[i]<=x)
{
f[i]=
1;
if(dfs(x-a[i],i+
1,num,len))
return 1;
f[i]=
0;
if(a[i]==x||x==len)
break;
while(
1)
if(a[i]==a[i+
1])
i++;
else
break;
}
return 0;
}
int main()
{
int maxn=
0;
scanf(
"%d",&n);
for(
int i=
1;i<=n;i++)
{
scanf(
"%d",&a[i]);
if(a[i]>
50)
{
i--;
n--;
continue;
}
maxn+=a[i];
}
sort(a+
1,a+n+
1,comp);
for(
int i=a[
1];i<=maxn;i++)
if(maxn%i==
0)
{
memset(f,
0,
sizeof(f));
sum=maxn/i;
if(dfs(i,
1,
0,i))
break;
}
printf(
"%d",ans);
return 0;
}
