POJ 1011 Sticks (DFS + 剪枝)

题目大意:

原来有很多根相同长度的木棒。乔治把这些木棒随意切成了 给出的长度。

问你他原来带来的那些相同长度的木棒的长度。

这个长度要最小。

思路：

强剪枝哦。。。

首先，你只需要枚举总和长度的约数 这个比较好想。

其次，你枚举到sum/2 还没有答案 就可以直接输出 sum了

这都好想

我们要事先排个序，按递减的顺序进行枚举。

后面，如果你进入dfs去枚举凑出一根木棒的 第一根木棒 （当然这根木棒是凑出来最长的）这根木棒找不到合适解 （return false）就剪掉。

相同的不用继续搜索。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; int a[70]; int n; bool vis[70]; bool first; vector
       
        X; int m; bool cmp(int a,int b) { return a>b; } bool ok() { for(int i=1;i<=n;i++) { if(!vis[i])return false; } return true; } bool dfs(int len,int most,int cnt,int pos)//枚举到的木棒当前的长度，对应的木棒要凑出的值，已经凑出来几根木棒，记录相同位置的一个临时变量 { if(cnt==m) return true; for(int i=1;i<=n;i++) { if(vis[i]||a[pos]==a[i])continue; if(len+a[i]==most) { vis[i]=true; if(dfs(0,most,cnt+1,0))return true; vis[i]=false; if(len==0)//第一根没有找到 { return false; } pos=i;//记录相同 } else if(len+a[i]