这个题剪枝比较多的说=。=
1.记录最长和最短的木棍，限制枚举的上下界
2.记录木棍的总长$tot$度，只在其能被枚举的长度整除时搜索
3.从长到短枚举长度(暂时好像没啥用)
4.每次(不是新的一根木棍时)从上次枚举的长度开始枚举(和3组合起来用的)
5.(强剪枝来了)如果是在尝试拼一根新木棍，那么只要没拼出来就拼不出来了(这个时候没有可以回溯的状态)
6.(也是一个强剪枝，和上面的一个道理)如果恰好拼出一根新木棍就拼不出来了，也是一定拼不出来了
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 int cnt[60]; 6 int n,rd,len,tot,num,maxx,mini=1e9; 7 bool DFS(int noww,int lenh,int last) 8 { 9 if(noww==num) return true; 10 for(int i=last;i>=mini;i--) 11 if(cnt[i]&&lenh+i<=len) 12 { 13 cnt[i]--; int tmp=lenh+i; 14 if(tmp==len) {if(DFS(noww+1,0,maxx)) return true;} 15 else {if(DFS(noww,tmp,i)) return true;} cnt[i]++; 16 if(!lenh||lenh+i==len) return false; 17 } 18 return false; 19 } 20 int main () 21 { 22 scanf("%d",&n); 23 for(int i=1;i<=n;i++) 24 { 25 scanf("%d",&rd); 26 if(rd<=50) 27 { 28 cnt[rd]++,tot+=rd; 29 maxx=max(maxx,rd); 30 mini=min(mini,rd); 31 } 32 } 33 bool found=false; 34 for(int i=maxx;i<=tot;i++) 35 if(tot%i==0) 36 { 37 len=i,num=tot/i; 38 if(DFS(0,0,maxx)) 39 { 40 printf("%d",i); 41 found=true; break; 42 } 43 } 44 if(!found) printf("%d",tot); 45 return 0; 46 }
原文：https://www.cnblogs.com/ydnhaha/p/9780181.html
