题目描述：
少林寺的宝贝“少林神棍”断成了n根长短不一的小木棒，现在要把这些小木棒重新拼若干跟等长的棍子，求棍长最短是多少？
先放上从这道题应该学到的经验：
1，要选择简合适的搜索顺序，如果一个人物分成多步，要优先尝试可能性少的。 （优先尝试长的木棒）
2，要发现表面上的不同，实质上等效的重复状态，避免重复。
3，根据实际问题，发现剪枝方案。
解题思路：
1，假设了一根棍子的长度的情况下，如何尝试去拼成若干根该长度的棍子？
2，本地的“状态是什么”？
3，初始状态和终止状态是什么？
4，状态如何转移？
具体不写了，去看看b站北大《算法基础》吧，讲的贼鸡儿好
ok，思考出上面几点之后，都不难写出dfs实现的代码：
#include <iostream> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int inf=0x3f3f3f3f; vector<int> q; //用普通数组貌似也没有不行 int n; int L; int used[60]; //第i根有没有用过 int dfs(int r,int m){ if(r==0 && m==0) return 1; if(m==0) m=L; for(int i=0;i<n;i++){ if(used[i]) continue; if(q[i]<=m){ used[i]=1; if(dfs(r-1,m-q[i])) return 1; else used[i]=0; } } return 0; } int main() { freopen("in.txt","r",stdin); int mark; while(1){ mark=0; int sl=0; //输入的总长 cin>>n; if(n==0) break; memset(used,0,sizeof(used)); q.clear(); for(int i=0;i<n;i++){ int t; cin>>t; sl+=t; q.push_back(t); } sort(q.begin(),q.end(),greater<int>()); //从大到小排序 // cout<<q.front(); for(L=q.front();L<=sl/2;L++){ if(sl%L!=0) continue; if(dfs(n,L)){ mark=1; cout<<L<<endl; } // cout<<"loved"; } if(!mark) cout<<1<<endl; } return 0; }
是的，这个代码通不过，理由是太慢了，这就引出了这节课的重点：剪枝
第一种剪枝方案：不要在同一位置多次尝试相同长度的木棒。
比如说有3根长度为52的木棒，如果第一次用长度52的木棒得不到答案，那么再遇到其他长度52的木棒就直接跳过就好了
第二种剪枝方案：如果拼某根棍子时，第一根木棒就拼不成，那就不要再换别的木棒尝试做第一根，直接拆前面(return上一层)的吧。因为，前面那个木棒你把它换掉，他一定会出现在后面的棍子里，后面的棍子也一样拼不成。
第三种剪枝方案：如果你后面的拼不成，希望把前面的某一根棍子的最后一根木棒拿掉，去拼后面的棍子，这种方法是行不通的，原因简单。
第四种剪枝方案：拼一根棍子，尽量里面的木棒是从长到短，因为可能一开始拼的1，3，2发现拼不成，拆掉2后拆掉3，因为按若出现前面的情况，按顺序2是在3后，3放1后面不行，下一步程序就会把2放一后面，就成了1，2，3显然这样子是没有意义的。
ac代码：
（明明四剪枝全加了还是不过，你猜怎么着？used数组开的不够。。。题目64我开的60，真悲哀）
#include <iostream> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int inf=0x3f3f3f3f; vector<int> q; //用普通数组貌似也没有不行 int n; int L; int jz4=0; //记录最近一次放上棍子的木棒下标 int used[70]; //第i根有没有用过 int dfs(int r,int m){ if(r==0 && m==0) return 1; if(m==0) m=L; int start=0; //剪枝4 if(m!=L) start=jz4+1; //剪枝4 for(int i=start;i<n;i++){ if(!used[i] && q[i]<=m){ if(i>0){if(q[i]==q[i-1] && used[i-1]==0) continue;} //剪枝一：相邻的相同长度的几根木棒，第一根不行，以后的也不行 used[i]=1; jz4=i; //剪枝4 if(dfs(r-1,m-q[i])) return 1; else{ used[i]=0; if( q[i]==m || m==L) return 0; //剪枝三：后面的拼不出，要拆前面的最后一棍，这是无效的，原因简单。剪枝二：如果第一根木棒就是不行的，那就换下一个数。 } //因为它在这儿不行，以后他注定还是要出现在某一根棍子最前面，就还是不行 } } return 0; } int main() { int mark; while(1){ mark=0; int sl=0; //输入的总长 cin>>n; if(n==0) break; memset(used,0,sizeof(used)); q.clear(); for(int i=0;i<n;i++){ int t; cin>>t; sl+=t; q.push_back(t); } sort(q.begin(),q.end(),greater<int>()); //从大到小排序 // cout<<q.front(); for(L=q.front();L<=sl/2;L++){ if(sl%L!=0) continue; if(dfs(n,L)){ mark=1; cout<<L<<endl; } // cout<<"loved"; } if(!mark) cout<<sl<<endl; } return 0; }