HDU-1455 剪枝

题意：有一堆的木棒，长度不一，它们是有一些整齐的木棒截断而成的，求最小的木棒原始长度。

我自己原本的思路就是搜索

你需要先找到一个目标长度，这个目标长度要满足

1. 是这些木棒总长的因数，就是说这个目标长度能被总长度整除
2. 目标长度要大于最长的木棍，因为所有木棍已经不分，只能合

 

然后我们一根一根找木棒，用一根标记一根，但是我们遇到了以下问题

如果1 2 2 3 7 7 5 6这种情况，你先把小的木棒（最灵活的木棒）给用完了，那大的木棒怎么拼也拼不成目标长度，显然需要DFS返回上不停返回，消耗大量的时间，所以我们应该先找到最长的木棒往下搜，（简单的说就是需要从大到小排序）

排完序后，比如目标长度为10，题目给   9 6 3 3  2 2 2 2 1，我们取的木棒是6  3   2    ，但是发现取3不行，那就所有的3就不必再继续拿来试了 ，直接跳过就行了

‘但是提交后还是超时，还有一种剪枝，就是当你确定目标长度后，开始拿木棍凑这个目标长度，发现第一根木棍给其他任意一根组合都不能组合成功，那就不需要继续搜索了，说明你的目标长度找错了，所以返回重新确立目标长度

然后我们回头看一下，一共几个剪枝

1. 目标长度大于等于目前小木棒的最大值，并且是总长度的因数
2. 从大到小给小木棒排序
3. 如果这个木棒不符合要求，那么跟这个木棒长度相同的木棒直接跳过
4. （最重要的剪枝 ） 因为已经排过序了，所以当你确立目标长度后，找出目前最长的木棒然后与其他木棒无法组成目标长度，那么就没必要继续往下搜索了，直接返回

上代码

#include<bits/stdc++.h>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF  0x3f3f3f3f
typedef long long  LL;
int a[70],n,f;
bool vis[70];
bool cmp(int a,int b){
    return a>b;
}
void dfs(int pos,int len,int g,int num){//当前下标、当前长度、目标长度、已匹配数量
    //printf("dfs: %d %d %d %d\n",pos,len,g,num);
    if(f)return;
    if(num==n){//所有树枝都匹配上了，说明有解
        f=1;
        return;
    }
    for(int i=pos;i<n;++i){
        if(!vis[i]&&a[i]+len<=g){
            vis[i]=1;
            if(a[i]+len==g){
                dfs(0,0,g,num+1);
            }else{
                dfs(i+1,a[i]+len,g,num+1);
            }
            vis[i]=0;//去除标记
            if(f)return;//找到了结果，返回
            if(len==0)return;//剪枝2，很关键!长度为零的时候选择木棒失败，要凑成某一目标长度的棍子，其中组成它的第一根小棍，怎么也无法和其他小棍凑出这个长度，那么没必要推翻这第一根小棍，直接推翻这个目标长度就可以了。


            while(i<n&&a[i+1]==a[i])++i;//剪枝3 由于所有棒子已降序排序，在DFS时，若某根棒子不合适，则跳过其后面所有与它等长的棒子；
        }
    }
}
int main(){
    int sum;
    while(scanf("%d",&n),n){
        memset(vis,0,sizeof(vis));
        sum=0;
        for(int i=0;i<n;++i){
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        sort(a,a+n,cmp);//从大到小排序，搜索的时候优先选择大的，减少冲突的情况
        for(int i=a[0];i<=sum;++i){
            if(i==sum)printf("%d\n",sum);//剪枝
            else if(sum%i==0){//剪枝1要测试的长度一定要是总长度的因数，否则就没有必要测试这个长度。因为棍子是一样长的，每一根的长度当然要是总长度的因数才对
                f=0;
                dfs(0,0,i,0);
                if(f==1){
                    printf("%d\n",i);
                    break;
                }
            }
        }
    }
}