pku1011 Sticks

#include<stdio.h>
#include<algorithm>

int g[65];
bool visit[65];
int length,amount,n;
bool exist;

void dfs(int pos,int curLen,int depth)
{
    if(depth==amount)
    {
        exist=true;
        return;
    }
    int pre=-1;        //当在整合某一长度失败后即可避免重复再搜索这个长度

    for(int i=pos;i<n;i++)
    {
        if(!visit[i]&&g[i]!=pre&&g[i]+curLen<=length)
        {
            pre=g[i];
            visit[i]=1;        

            if(g[i]+curLen==length) dfs(0,0,depth+1); //这里和main中的pos=0同义，首先毫无判断的选择剩余未用小木棍中最长的    

            else dfs(i+1,curLen+g[i],depth);

            visit[i]=0;                                    //回溯时visit清零必须位于后面剪枝的前面

            if(pos==0||exist) return;
                    //每当还原一根新的木棍时，必定首先从剩余未用的小木棍中毫无判断的选择最长的，然后再搜索找一些较小的长度凑零头

                    //而当整合这个当前最长的小木棍失败时直接说明已还原的木棍的组分有问题，因为每个小木棍最终都必须整合到某一个木棍中，

                    //剩下的最长的小木棍凑合剩下的一些小木棍而不能整合这个最长的，那么这个剩下的最长的小木棍是不可能被整合到某一根

                    //木棍中，因而即可直接return到还原第depth-1根木棍，只有当搜索零头失败时才需要回溯，通过for迭代到下一个零头去dfs

        }
    }
}

int cmp(const void *a,const void *b)
{
    return *(int *)b-*(int *)a;
}

int main()
{
    while(scanf("%d",&n),n)
    {
        int sum=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&g[i]);
            sum+=g[i];
        }

        qsort(g,n,sizeof(int),cmp);        //将棍长从大到小排序

        exist=false;
        for(length=g[0];length<=sum;length++)
        {
            if(sum%length==0)
            {
                amount=sum/length;
                for(int i=0;i<n;i++) visit[i]=0;
                dfs(0,0,0);
                if(exist)
                {
                    printf("%d\n",length);
                    break;
                }
            }
        }
    }
    return 0;
}

总结：

非常经典的一道剪枝题，透过剪枝，可以更深层次理解dfs