poj1011---DFS

题目的大意是给了你有限个棍子以及每个棍子的长度，而且所有的棍子都是由有限个长度相同的棍子截断得到的，让你求被截棍子的最小长度

搜索剪枝神题，做的我够呛

提供一个比较好的解题报告  http://www.cnblogs.com/mycapple/archive/2012/08/14/2638430.html

比较奇怪的是数组开小了WA了，开大就过了

代码还是比较挫的

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;

int shu[299];
int hash[299];
int feng,n,ok,chu,fail;
int nhash[299];

void dfs(int all,int add)
{
    int i;
    if(add==chu){
        ok=1;return ;
    }
    if(ok==1||fail==1){
        return ;
    }
    if(all>0&&hash[1]==0){ //第一根木棍没有被利用，就结束整个搜索
        fail=1;return;
    }

    for(i=1;i<=n;i++){
        if(hash[i]==1)continue;

        if(all==(add*feng)){
            if(hash[i-1]==0){//当前的第一根木棍 组成一定要成功
                return;
            }
        }
        if((all+shu[i])<=((add+1)*feng)){
            if(shu[i-1]==shu[i]&&hash[i-1]==0)continue;
            hash[i]=1;
            if((all+shu[i])==((add+1)*feng))
                dfs(all+shu[i],add+1);
            else
                dfs(all+shu[i],add);
            hash[i]=0;
        }
    }
}

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

int main()
{
    int all,i,j;
    while(scanf("%d",&n)!=EOF){
        if(n==0)return 0;
        int max=0,temp;
        all=0;

        for(i=1;i<=n;i++){
            scanf("%d",&shu[i]);
            all+=shu[i];
            if(shu[i]>max)max=shu[i];
        }
        sort(&shu[1],&shu[n+1],cmp);

        for(i=max;i<=all;i++){
            if(all%i!=0)continue;
            for(j=0;j<=n;j++)hash[i]=0;
            hash[0]=1;
            feng=i;
            chu=all/i;
            fail=0;
            ok=0;
            dfs(0,0);
            if(ok==1)break;
        }

        printf("%d
",feng);
    }

    return 0;
}