这题的思路是从书上看来的,不过好歹也弄明白原因了;
注释清楚 方便以后看看.
题意是 有若干 长度相同的棍子..英语水平有限,一开始没看懂,以为只有1根,要多多练习啊..
1 #include<iostream> 2 #include<algorithm> 3 #define maxn 70 4 using namespace std; 5 int stick[maxn]; 6 bool visit[maxn]; 7 int length,pos,num,n,sum; 8 int cmp(int x,int y) 9 { 10 return x>y ; 11 } 12 bool dfs(int count,int now,int pos) 13 { 14 int i; 15 bool sign=(now==0?true:false);//标记当前长度 16 if(count==num) return true; 17 for(i=pos;i<n;i++) 18 { 19 if(visit[i]) continue;//用过了就不用考虑了 20 if(now+stick[i]==length) 21 { 22 visit[i]=true;//标记棍子是否使用 23 if(dfs(count+1,0,0))//已经完成当前棍子匹配,进行下一根棍子的的匹配 24 return true; 25 visit[i]=false;//无法完成匹配,则应重置 26 return false; 27 } 28 29 else if(now+stick[i]<length) 30 { 31 visit[i]=true; 32 if(dfs(count,now+stick[i],i))//继续搜索没有用过的棍子以完成匹配 33 return true; 34 visit[i]=false; 35 if(sign) return false;//长度为0说明当前长度匹配不成功,继续下一个长度的搜索; 36 while(stick[i]==stick[i+1]) i++;//重要剪枝,相同长度的棍子没必要再搜索 37 } 38 } 39 return false; 40 41 } 42 int main() 43 { 44 //freopen("1455.txt","r",stdin); 45 int i; 46 while(~scanf("%d",&n),n) 47 { 48 sum=0; 49 for(i=0;i<n;i++) 50 scanf("%d",stick+i),sum+=stick[i]; 51 sort(stick,stick+n,cmp);//从大到小排; 52 for(length=stick[0];length<=sum;length++) 53 { 54 if(sum%length==0) 55 { 56 num=sum/length; 57 memset(visit,false,sizeof(visit)); 58 if(dfs(1,0,0)) 59 { 60 printf("%d ",length); 61 break; 62 } 63 } 64 } 65 } 66 return 0; 67 }