地址:http://poj.org/problem?id=1011
剪枝:
1、 因为所有原始棒子等长,那么必有总长度可整除初始长度
2、 从折断后的最长棒开始搜索,直到sumlen-maxlen,若出现符合的长度则输出,否则输出sumlen;
3、 由于所有棒子已降序排序,在DFS时,若某根棒子不合适,则后面所有与它等长的棒子一定不适合(后面比前面少了一根同自己相同的棒子可用,其余都相同);
4、 若当前不能构成一个目标长度的棒子,显然此时的假设值是错的,直接返回false。
#include<iostream> #include<cstring> #include<algorithm> using namespace std; int initlen;//目标长度 int n; //木棒个数 int len[70]; bool ul[70]; int sumlen; bool cmp(const int a,const int b){ return a>b; } bool dfs(int nowlen,int point,int num){//nowlen为当前组合长度,point是当前搭配的位置,num为当前已使用的木棒数 if(num==n) return 1; int sample = -1; for(int i = point;i<n;i++){ if(ul[i]||len[i]==sample) continue;//相同的树枝是没有意义的,前面的不能得到true后面的更没可能 ul[i]=1; if(nowlen+len[i]<initlen){ if(dfs(nowlen+len[i],i,num+1)) return 1; else sample = len[i]; } else if(nowlen+len[i]==initlen){ if(dfs(0,0,num+1)) return 1; else sample = len[i]; } ul[i]=0; if(nowlen==0) break; } return 0; } int main(){ int i,j; while(cin>>n&&n){ memset(ul,0,sizeof(ul)); sumlen = 0; for(i=0;i<n;i++){ cin>>len[i]; sumlen+=len[i]; } bool flag = 0; sort(len,len+n,cmp); for(initlen = len[0];initlen<=sumlen-initlen;initlen++){ if(sumlen%initlen==0&&dfs(0,0,0)){ flag = 1; cout<<initlen<<endl; break; } } if(!flag) cout<<sumlen<<endl; } return 0; }