dfs搜索+剪枝

 

1.原棒可能的长度len：最长的小棒<=len<=所有小棒长度和sum  and  sum%len==0

2.dfs的参数：len、leftlen当前要拼的原棒剩下的长度、num剩下的小棒的个数、last上层dfs用的小棒序号+1，为避免重复，这次从last向后试探

3.剪枝：

　　1剪枝：若当前木棒不可用，那么与这根小木棒长度相同的木棒也将不可用，直接跳过

　　2剪枝：若这个小木棒的长度刚好是leftlen的长度，并且不能成功，那么说明后面的不用试了，因为如此合适的小棒被接收都不能导至试探成功，后面的小棒更不可能，直接返回false（试探失败 ）

　　3剪枝：如果len=remains_len（说明这是新一根原棒，还没有进行匹配），而在预先判断匹配与否时已经判断不能匹配，这样都不能匹配，那么说明以后都不能匹配了（这就是深搜的效果了）。返回0（试探失败）  //这是我从别人题解上抄的，很重要的一个剪枝，但是不理解。

 

代码：

#include
     
      #include
      
       using namespace std;int n,sum;int a[69];bool vis[69];bool cnt(int a,int b){    return a>b;}bool dfs(int len,int leftlen,int num,int last){    if(leftlen==0){        if(num==0)return true;//成功         else leftlen=len,last=1;//开始搜索新的一根原棒     }        for(int i=last;i<=n;i++){        if(vis[i]==false&&a[i]<=leftlen){            vis[i]=true;            bool temp=dfs(len,leftlen-a[i],num-1,i+1);            vis[i]=false;            if(temp)return true;            else{                if(a[i]==leftlen||len==leftlen)return false;                while(a[i]==a[i+1])i++;            }        }    }    return false;}int main(){    cin>>n;    for(int i=1;i<=n;i++){        cin>>a[i];        sum+=a[i];    }    sort(a+1,a+1+n,cnt);        for(int len=a[1];len<=sum;len++){        if(sum%len==0){            if(dfs(len,len,n,1)){                cout<
       
        <