hdu 1455(Sticks 고전 심층 검색)

 
   

     9 5 2 1 5 2 1 5 2 1 4 1 2 3 4 0 
   
 
  

 
   

     6 5 
   
 
  

思路：（1）题意从另一个角度可以这样理解，现有的n个有各自长度的木棍怎么组合拼接成k个木棍，使得k根木棍的长度相同。。那么肯定有很多种组合方法，现在要找到k根木棍长度最小的那种方法；

            （2）经典深搜：将这n根木棍长度从大到小排序，并且求出n根木棍的总长度sum,  那么再想：最小值minn的范围肯定是在stick[0].lenth~sum之间，对吧/ ///，如果sum%minn==0(stick[0].lenth<=min<=sum)

说明i有可能成为最小值，接下来就是具体确定怎么拼接成长度为minn的若干个木棍；

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

int n,cnt,sum;//      ，n       ，sum  n       ，cnt=sum/i;

struct node
{
  int lenth //      
  int mark; //           ;
}stick[66];

int cmp(node a,node b) //         
{
    return a.lenth>b.lenth;
}

//len        ，count           ，
int dfs(int len,int count,int l,int pos)
{
   if(len==sum) return 1; //    
   if(count==cnt)   return 1;

   for(int i=pos;i(stick[i].lenth+l))
      {
          stick[i].mark=1;
          l+=stick[i].lenth;
          if(dfs(len,count,l,i+1))
             return 1;
          l-=stick[i].lenth;  //      ，     
          stick[i].mark=0;
          if(l==0) return 0;
          while(stick[i].lenth==stick[i+1].lenth)i++;  //         140MS，         31MS，ORZ
      }
   }
  return 0;
}

int main()
{
        while(cin>>n&&n)
        {
           cnt=sum=0;
           for(int i=0;i>stick[i].lenth;
               sum+=stick[i].lenth;
               stick[i].mark=0;
           }
           sort(stick,stick+n,cmp);
           for(int i=stick[0].lenth;i<=sum;i++)
           {
              if(sum%i)continue;
              cnt=sum/i;  
              if(dfs(i,0,0,0))
              {
                 printf("%d
",i);
                 break;
              }
           }

        }
        return 0;
}