1.初始木棍的长度必须是所有木棍长度之和的约数
2.按木棍的递减顺序搜索
3.构造一根初始木棍的第一根木棍必须是最长的
4.2根长度相同的木棍没必要重复搜索
#include<stdio.h> #include<algorithm> #include<string.h> int s[70],v,n; bool mark[70],flag; bool cmp(int a,int b) { return a>b; } void dfs(int w,int sum)//w为长度为l的剩余长度,sum为总的剩余长度 { int i; if(sum==0) flag=0; else for(i=0;i<n&&flag;i++) { if(mark[i]==0&&w-s[i]>=0) { mark[i]=1; if(w-s[i]==0) dfs(v,sum-s[i]); else dfs(w-s[i],sum-s[i]); mark[i]=0; if(w==s[i])return ; //如果剩余的要求的长度和目前的相同;已经做过了不行的话,意味这v是不符合的 if(w==v&&s[i]<v) return ;//如果剩下的长度刚从v开始时,然而s[i]比v小不行的话,那也是不行的 while(s[i]==s[i+1])i++; //这个意思是如果s[i]长度的不符合,那这个长度的都不符合 } } } int main() { int i,sum; while(scanf("%d",&n),n) { sum=0; flag=1; for(i=0;i<n;i++) { scanf("%d",&s[i]); sum+=s[i]; } std::sort(s,s+n,cmp); //由大到小排序 for(v=s[0];v<=sum;v++) //从最大的长度到总长度,一个一个尝试,直到找到符合的 if(sum%v==0) { if(sum==v) printf("%d\n",v); else { memset(mark,0,sizeof(mark)); dfs(v,sum); if(!flag) { printf("%d\n",v); break; } } } } return 0; }