题意

• 给定n根短棍，将其拼成若干等长的长棍，求能拼成的长棍的最短长度是多少

思路

• 枚举长棍的长度，深搜判断能否拼成（将每一个棍尝试摆上去，如果摆上去不大于枚举长度就深搜下一层，超过的就跳过，最终判断所有棍用完的时候，最后一根长棍是否刚好拼完）
• 优化一：对于枚举，枚举区间为最长的棍的长度到所有棍的长度和，且不能被总和整除的直接跳过
• 深搜优化一：对于所有短棍，先放短的再放长的，剪掉短的用完后长的无法拼成的情况
• 深搜优化二：对于一根短棍，如果回溯回到它（它放的有问题），说明则跳过所有和它等长的短棍
• 深搜优化三：如果回溯到的短棍是一根长棍的结尾，则换成比他短的一定不会更优，所以说明换成短的没有意义，换成长的不合法，应当直接再次回溯，重新枚举倒数第二根；同样地，如果回溯到的是开头，说明上一根有问题/这个长度不成立
• 深搜优化四：对于组成长棍的短棍，越往后约束条件越严，所以后面部分选取短棍时，一定不会选择比上一根短棍更长（序号更小）的短棍，除非是新开了一根长棍，故开last来减少深搜内的枚举次数
• 以上优化少任何一个都无法AC

AC代码

#include<bits/stdc++.h>
using namespace std;
int a[100],vis[100],n;
bool dfs(int len,int rg,int rl,int last){
	if(rg==0&&rl==0) return true;
	if(rl==0) {rl=len;last=-1;}
	for(int i=last+1;i<n;i++){
		if(vis[i]) continue;
		if(a[i]>rl) continue;
		vis[i]=1;
		if(dfs(len,rg-1,rl-a[i],i)){
//			cout<<rl-a[i]<<' '<<i<<' '<<a[i]<<'\n';
			return true;
		}
		vis[i]=0;
		if(a[i]==rl||len==rl)return false;
		while(a[i]==a[i+1])i++;
	}   
	return false;
}
bool cmp(int a,int b){return a>b;}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	int sum=0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	sort(a,a+n,cmp);
	for(int i=a[0];i<=sum;i++){
		if(sum%i!=0)continue;
		memset(vis,0,sizeof(vis));
		if(dfs(i,n,i,-1)==1){
			cout<<i<<'\n';
			break;
		}

	}
	
	return 0;
}