【uva307】小木棍 Sticks [dfs搜索]

本文主要是介绍【uva307】小木棍 Sticks [dfs搜索]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVA307 小木棍 Sticks

我枯辽

然后导致一直爆炸，就是调试一直就跳回初始状态然后就输出sum 我的一上午就这样么得了

还有关于小蓝书上面的程序是错但剪枝是真的阔以就是有一些奇奇怪怪我看不懂的剪枝

关于剪枝

sum一定能被原长度整除木棍的长度一定大于等于所有木棍中最长的那一根
将木棍长度从大到小排因为拼长度为a b的两个木棍 ab和ba的先后顺序是等效的只需要搜索其中一种即可
相同的长度的木棍不用多次搜若当前长度拼不出来的话另外相同的长度也拼不出来所以得跳过
如果在一根木棒中尝试拼接的第一根木棍的递归分支就以失败返回，直接判断当前分支无解
如果两个木棍的长度和与一个木棍的一样，只尝试一个的就行了(因为前两个可能会有更大的效用) （这个我不太理解emmmmmm）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=100+5; 
 4 bool v[N];
 5 int len,n,a[N],sum,m;
 6 template<class t>void rd(t &x)
 7 {
 8     x=0;int w=0;char ch=0;
 9     while(!isdigit(ch)) w|=ch=='-',ch=getchar();
10     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
11     x=w?-x:x;
12 }
13 bool cmp(int a,int b) {return a>b;}
14 
15 bool dfs(int cnt,int l,int last)
16 {
17     if(cnt==m) return 1;
18     if(l==len) return dfs(cnt+1,0,1);
19     int fail=0;
20     for(int i=last;i<=n;i++)
21     {
22         if(v[i]==0&&a[i]+l<=len&&fail!=a[i])
23         {
24             v[i]=1;
25             if(dfs(cnt,l+a[i],i)) return 1;
26             v[i]=0;fail=a[i];//回溯 当前长度失败了 
27             if(l==0||l+a[i]==len) return 0;
28         }
29     }
30     return 0;
31 }
32 
33 int main()
34 {
35     while(scanf("%d",&n)&&n)
36     {
37         sum=0;
38         for(int i=1;i<=n;i++) {rd(a[i]);sum+=a[i];}
39         sort(a+1,a+n+1,cmp);//排序 
40         for(len=a[1];len<=(sum>>1);len++)
41         {
42              if(sum%len) continue;
43              m=sum/len;
44              memset(v,0,sizeof(v));
45              if(dfs(1,0,1)) {printf("%d\n",len); break;}
46         }
47         if(len>sum>>1) printf("%d\n",sum);
48     }
49         return 0;
50 }