https://www.luogu.org/problem/show?pid=1120
题目描述
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
输入输出格式
输入格式： 输入文件共有二行。
第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤65
（管理员注：要把超过50的长度自觉过滤掉，坑了很多人了！）
第二行为N个用空个隔开的正整数，表示N根小木棍的长度。
输出格式： 输出文件仅一行，表示要求的原始木棍的最小可能长度
输入输出样例
输入样例#1： 9 5 2 1 5 2 1 5 2 1 输出样例#1： 6
极致的剪枝 去掉基本上所有的重复性运算
若剩下的余量比最小的小，减掉 剩下的比余量的大 减掉 重复的数据不在一个空间内枚举 若一个数头和后面有重复 则减掉。 如果一个开头没有找到等于l的匹配 减掉。
#include <bits/stdc++.h> using namespace std; int n; int a[1000]; int tag[1000]; int ss[1000]; int sum,z,ll; void dfs(int s,int r,int l,int t); bool cmp(int x,int y) { return x>y; } void frun(int t,int l) { if(t==sum/l-1) z=1; if(z) return ; for(int i=0;i<ll;i++) { if(!tag[i]) { //cout<<s<<' '<<a[i]<<' '<<t<<endl; tag[i]=1; dfs(a[i],i,l,t); tag[i]=0; break; } } } void dfs(int s,int r,int l,int t) { if(z) return ; if(s==l) { frun(t+1,l); } if(l-s>ss[r]||l-s<a[ll-1]) return ; for(int i=r;i<ll;i++) { if(s+a[i]<=l&&!tag[i]) { if(l-s>ss[i]||z) return ; //cout<<s<<' '<<a[i]<<' '<<t<<endl; tag[i]=1; dfs(s+a[i],i+1,l,t); tag[i]=0; if(l-s==a[i]) return ; for(;i<ll;i++) if(a[i]!=a[i+1]) break; } } } int main() { while(cin>>n) { memset(ss,0,sizeof(ss)); sum=0; int x;ll=0; for(int i=0;i<n;i++) { cin>>x; if(x<=50) { a[ll]=x; sum+=a[ll]; ll++; } } for(int i=ll-1;i>=0;i--) { ss[i]=a[i]+ss[i+1]; } sort(a,a+ll,cmp); //cout<<sum<<endl; z=0; for(int i=a[0];i<=sum/2;i++) { if(sum%i==0) { frun(0,i); if(z) { cout<<i<<endl; break; } } } if(!z) cout<<sum<<endl; } }