Sticks(dfs+枝剪练习)

Sticks

原题

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 50 个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序，帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。

解法

dfs+剪枝
这道题剪枝可分为这样几种
1 首先 木棍总和的sum 一定可以整除 木棒个数idx 从而得到每一个木棍长度
2 其次 我们枚举木棍长度肯定从所有木棍中最大的木棍枚举到木棍总和 sum/2 否则就只有一根木棒
3 然后 我们在枚举每一个木棍时我们可以先挑长木棍，然后查漏补缺 因为小木棍可以拼接的种数很多
4 并且 我们枚举时 如果枚举到当前 s1木棍发现不行 我们 对等于 s1 的木棍也不考虑，因为如果等于 s1 的木棍拼接某一段是可行的 那 s1 按理来说对于这一节也是可行的 这是冗余性剪枝
5 还有 我们如果拼接当前木棍失败了 并且当前木棍一根都没拼 那可以直接返回上一个木棒不用管他了

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int const N = 70;
int n,sum,idx,f;
int g[N],d[N];
bool cmp(const int &a,const int &b){
    return a>b;}
bool dfs(int id,int l,int k){
    if(f) return true;if(id>idx){
    f=1;cout<<sum/idx<<endl;return true;}if(l==sum/idx) {
    return dfs(id+1,0,1);}for(int i=k;i<=n;i++){
    if(d[i]) continue;if(l+g[i]>sum/idx) continue;if(!d[i-1]&&g[i]==g[i-1]) continue;d[i]=1;if(dfs(id,l+g[i],i+1)) return true;d[i]=0;if(!l||l+g[i]==sum/idx) return false;}return false;
}
int main(){
    while(cin>>n&&n){
    sum = f = 0;for(int i=1;i<=n;i++) cin>>g[i],sum+=g[i];sort(g+1,g+1+n,cmp);for(int i=g[1];i<=sum/2;i++){
    if(sum%i) continue;//不能整除先排除memset(d,0,sizeof d);idx=sum/i;f=0;if(dfs(1,0,1)) break;}if(!f) cout<<sum<<endl;}return 0;
}