讲的大致是几根原本长度相同的木棒，然后被某人当出气筒剪啊剪啊，剪成好几段，然后，好吧，这时间一长记性就差了，忘了原来这堆木棒的长度。。。orz，我这若菜，也只能帮您推算出原来这堆木棒的可能的最短长度了。。。
搜索中的经典之经典，必须掌握啊。。。。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 struct stick{ 7 int length; //长度 8 int mark; //标记是否被使用过 9 }; 10 stick sticks[64]; 11 int n,num,sum; 12 13 int cmp(const stick &s1,const stick &s2){ 14 return s1.length>s2.length; 15 } 16 //len当前的长度，count当前长度为len的木棒的根数 17 int dfs(int len,int l,int count,int pos){ 18 if(len==sum)return 1;//如果当期的长度就是所有木棒的总长 19 if(count==num)return 1; 20 for(int i=pos;i<n;i++){ 21 if(sticks[i].mark)continue; 22 //没有被标记过的 23 if(len==(sticks[i].length+l)){ 24 sticks[i].mark=1; 25 if(dfs(len,0,count+1,0))//长度相等时，还是要从第一根开始搜 26 return 1; 27 sticks[i].mark=0; 28 return 0; 29 }else if(len>(sticks[i].length+l)){ 30 sticks[i].mark=1; 31 l+=sticks[i].length; 32 if(dfs(len,l,count,i+1)) 33 return 1; 34 l-=sticks[i].length;//如果不成功，就要恢复 35 sticks[i].mark=0; 36 if(l==0)return 0;//当前搜索，如果前面的l为0，但第一根没有用上，那么这根木棒就要舍弃 37 while(sticks[i].length==sticks[i+1].length)i++;//这根不成功的话，则相连的长度相同的不要 38 } 39 } 40 return 0; 41 } 42 43 int main(){ 44 while(scanf("%d",&n)!=EOF){ 45 if(n==0)break; 46 sum=0; 47 for(int i=0;i<n;i++){ 48 scanf("%d",&sticks[i].length); 49 sticks[i].mark=0; 50 sum+=sticks[i].length; 51 } 52 sort(sticks,sticks+n,cmp); 53 for(int len=sticks[0].length;len<=sum;len++){ 54 if(sum%len)continue; 55 num=sum/len; //原来长度为len的木棒的根数 56 if(dfs(len,0,0,0)){ 57 printf("%d\n",len); 58 break; 59 } 60 } 61 } 62 return 0; 63 }