HDU1455（dfs+各种剪枝）

题目大意：给你n个小树枝，问你能够将其拼成的s根相同长度的大树枝，问这个长度最小为多少？

解题思路：排序后dfs，记住一点的是如果第一根树枝不能拼成想要到达的长度的话后面就不用看了，剪枝

AC代码如下：

#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<queue>
#include<stack>
using namespace std;

int cmp(int a,int b)
{
    return a>b;
}

int data[100],num,flag,book[100];

void dfs(int x,int len,int hope,int size)
{
    if(flag) return ;
    if(size==num)
    {
        flag=1;
        return ;
    }
    for(int i=x;i<=num;i++)
    {
        if(!book[i] && data[i]+len<=hope)
        {
            book[i]=1;
            if(data[i]+len==hope)
                dfs(1,0,hope,size+1);
            else
                dfs(i+1,len+data[i],hope,size+1);
            if(flag) return ;
            book[i]=0;
            if(len==0) return ;  //第一根不能拼成hope的话减掉
            while(i<num && data[i+1]==data[i]) i++;  
        }
    }
    return ;
}

int main()
{
    int i,j,sum;
    while(cin>>num && num)
    {
        sum=0;
        for(i=1;i<=num;i++)
        {
            cin>>data[i];
            sum+=data[i];
        }
        sort(data+1,data+1+num,cmp);
        for(i=data[num];i<=sum;i++)
        {
            memset(book,0,sizeof(book));
            flag=0;
            if(sum%i==0)
            {
                dfs(1,0,i,0);
                if(flag)
                {
                    cout<<i<<endl;
                    break;
                }
            }
        }
    }
    return 0;
}