hdu 1455 Sticks(經典搜索)

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,map[70],v[70];
int sum;//所有木棒的長度和
int total,length,flag;
bool cmp(int x,int y)
{
    return x > y;
}
//num表示組成木棒的個數，len表示已組成的長度，pos表示木棒的位置
void dfs(int num,int len,int pos)
{
    if(num == total)
    {
        flag = 1;
        return;
    }
    if(flag) return ;
    for(int i = pos ; i < n ; i ++)
    {
        if(v[i]) continue;
        if(map[i] + len == length)
        {
            v[i] = 1;
            dfs(num + 1,0,0);//成功組合成一個木棒，num+1
            v[i] = 0;
        }
        else if(map[i] + len < length)
        {
            v[i] = 1;
            dfs(num ,map[i] + len,i + 1);
            v[i] = 0;
            if(len == 0) return;/*如果當前搜索時，前邊的長度為0，而第一根沒有成功的使用，說明第一根始終要被廢棄，所以這種組合必定不會成功*/
            while(map[i] == map[i + 1])//這跟不符合要求的話，則長度相同的也不符合要求，直接跳過
            i++;
        }
    }
}
int main()
{
    int i;
    while(scanf("%d",&n) && n)
    {
        sum = 0;
        for(i = 0 ; i < n ; i ++)
        {
            scanf("%d",&map[i]);
            sum += map[i];
        }
        memset(v,0,sizeof(v));
        sort(map,map + n,cmp);//將木棒從長到短進行排序
        for(length = map[0] ; length <= sum ; length ++)/*從最長的那根木棒開始搜索，因為組合而成的木棒長度最小的也大於等於原本最長的那根*/
        {
            if(sum%length) continue;//如果不能被整除說明不能組成整數根木棒
            flag = 0 ;//標記
            total = sum/length;//以length為組合後的長度，total表示得到木棒的個數
            dfs(1,0,0);
            if(flag)
            {
                printf("%d\n",length);
                break;
            }
        }
    }
    return 0;
}