木棒(dfs+剪枝优化)

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过50个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序，帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

输入格式

输入包含多组数据，每组数据包括两行。

第一行是一个不超过64的整数，表示砍断之后共有多少节木棍。

第二行是截断以后，所得到的各节木棍的长度。

在最后一组数据之后，是一个零。

输出格式

为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

数据范围

数据保证每一节木棍的长度均不大于50。

输入样例：

  

   

    

     

    
    

     

      9
     
    
   

    

     

    
    

     

      5 2 1 5 2 1 5 2 1
     
    
   

    

     

    
    

     

      4
     
    
   

    

     

    
    

     

      1 2 3 4
     
    
   

    

     

    
    

     

      0
     
    
  

输出样例：

  

   

    

     

    
    

     

      6
     
    
   

    

     

    
    

     

      5
     
    
  

 思路：从小到大枚举每个可能的最小长度，一旦满足要求就输出并break；

因为输入的每节木棍都是由一开始是等长的若干根木棒分割出来的，所以一开始那若干根木棒的最小长度minlen应该能整除输入的所有木棍之和sum，

即minlen满足：sum%minlen==0，并且可以恰好由这n根木棍拼接出来（输入的每节木棍都要用上，当然>50的除外）；

minlen最小应该是那n根木棍的最大长度，因为如果minlen<那n根木棍的最大长度，那用长度等于最大长度的木棍无法达到minlen（不可能将其折断），所以minlen应该从那n根木棍的最大长度开始枚举；

判断长度=当前最小长度minlen的若干木棒能否由这n根木棍拼接出来，可以用dfs搜索，但是要剪枝优化，不然会超时！

注（dfs剪枝的几个方面）：

1、搜索顺序（优先搜索决策少的）

2、排除冗余信息（去掉重复的，没有用的）

3、可行性剪枝（如果当前方案到当前位置可以判断出已经不能继续执行，则return）

4、最优性剪枝（如果当前不是最优，则return）

4、记忆化剪枝（类似dp）

在这里，

1、先优化搜索顺序，因为对于固定minlen，可选择长度大的木棍较少，相当于对于固定区间可选择的长度大的子区间个数较少（因为长度大了，可浮动的范围较小），所以长度大的决策少，先用长度的大的拼接；

2、木棍的编号默认按递增的顺序，这样就保证了不会得出因某根木棍的顺序不一样的不同方案（某根木棍在前在后都一样）；3、当发现第一个用来拼接的木棍dfs后不能return true后，直接判定用当前minlen无法实现，直接return false（因为每根木棍都要用到，当前当前这根木棍不行，之后不管什么时候都不能用这根木棍）；

4、同理，最后一根用来拼接的木棍dfs后不能return true后，直接判定当前方案false；

5、如果中间过程中出现某根木棍不能用，则在拼接当前这根木棒的进程中将所有与之等长的木棍都pass，直接用下一个长度木棍继续拼接；

完整代码：

  

   

    

     

    
    

     

      #include <cstring>
     
    
   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     

      const 
      int maxn=
      70;
     
    
   

    

     

    
    

     

      using 
      namespace 
      std;
     
    
   

    

     

    
    

     

      bool vis[maxn];
      //vis[i]表示编号为i的木棍是否被用过（是否能用），true表示用过了（不能用了），false（没用过，能用）
     
    
   

    

     

    
    

     

      int n,sum,minlen,sticks[maxn];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      bool dfs(int cnt,int len,int pos)//cnt表示当前已经拼到第cnt根木棒，len表示当前这跟木棒的已经拼接的长度，pos表示枚举木棍的起点位置
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    
      if(cnt*minlen==sum) 
      return 
      true;
      //当前拼成的木棒根数*当前每根木棒的长度=sum时，当前方案实现了，所以return true
     
    
   

    

     

    
    

     
    
      if(len==minlen) 
      return dfs(cnt+
      1,
      0,
      0);
      //当前正在拼的这根木棒的长度=当前每根木棒的长度时，表示这根拼完了，继续从0开始拼下一根，cnt+1
     
    
   

    

     

    
    

     
    
      for(
      int i=pos;i<n;i++){
      //剪枝2：按编号递增枚举
     
    
   

    

     

    
    

     
        
      if(vis[i]) 
      continue;
     
    
   

    

     

    
    

     
        
      int l=sticks[i];
     
    
   

    

     

    
    

     
        
      if(len+l<=minlen){
     
    
   

    

     

    
    

     

                  vis[i]=
      true;
     
    
   

    

     

    
    

     
            
      if(dfs(cnt,len+l,i+
      1)) 
      return 
      true;
     
    
   

    

     

    
    

     

                  vis[i]=
      false;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
            
      if(!len) 
      return 
      false;
      //剪枝3：当发现第一个用来拼接的木棍dfs后不能return true后，直接判定用当前minlen无法实现，直接return false
     
    
   

    

     

    
    

     
            
      if(len+l==minlen) 
      return 
      false;
      //剪枝4：同理，最后一根用来拼接的木棍dfs后不能return true后，直接判定当前方案false；
     
    
   

    

     

    
    

     
            
      int j=i;
     
    
   

    

     

    
    

     
            
      while(j<n&&sticks[j]==l) j++;
      //剪枝5：如果中间过程中出现某根木棍不能用，则在拼接当前这根木棒的进程中将所有与之等长的木棍都pass，直接用下一个长度木棍继续拼接；
     
    
   

    

     

    
    

     

                  i=j
      -1;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
      return 
      false;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          ios::sync_with_stdio(
      false);
     
    
   

    

     

    
    

     
    
      cin.tie(
      0);
     
    
   

    

     

    
    

     
    
      while(
      cin>>n&&n){
     
    
   

    

     

    
    

     

              sum=
      0,minlen=
      0;
      //sum表示n根木棍长度之和，minlen表示n根木棍的最大长度，即：一开始的最小可能长度
     
    
   

    

     

    
    

     
        
      memset(vis,
      false,
      sizeof vis);
     
    
   

    

     

    
    

     
        
      for(
      int i=
      0;i<n;i++){
     
    
   

    

     

    
    

     
            
      cin>>sticks[i];
     
    
   

    

     

    
    

     
            
      if(sticks[i]>
      50) 
      continue;
      //pass调>50的数据
     
    
   

    

     

    
    

     

                  sum+=sticks[i];
     
    
   

    

     

    
    

     

                  minlen=max(minlen,sticks[i]);
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

              sort(sticks,sticks+n);
     
    
   

    

     

    
    

     

              reverse(sticks,sticks+n);
      //剪枝1：将sticks按从大到小排
     
    
   

    

     

    
    

     
        
      for(
      int i=
      0;i<n;i++){
     
    
   

    

     

    
    

     
            
      if(sticks[i]>
      50){
     
    
   

    

     

    
    

     

                      vis[i]=
      true;
      //pass掉>50的数据
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        
      while(
      true){
     
    
   

    

     

    
    

     
            
      if(sum%minlen==
      0&&dfs(
      0,
      0,
      0)){
     
    
   

    

     

    
    

     
                
      cout<<minlen<<
      endl;
     
    
   

    

     

    
    

     
                
      break;
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

                  minlen++;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
      return 
      0;
     
    
   

    

     

    
    

     

      }