hdu 1455 Sticks

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int st[65];
bool vis[65];
int cnt;
int n;
int l;
bool cmp(int a,int b)
{
    return a>=b;
}
bool dfs(int num,int len)
{
    if(num==cnt) return true;
    for(int i=0;i<n;i++)
    {
        if(!vis[i])
        {
            if(len+st[i]==l)
            {
                vis[i]=true;
                if(dfs(num+1,0)) return true;
                vis[i]=false;

            }
            if(len+st[i]<l)
            {
                vis[i]=true;
                if(dfs(num,len+st[i])) return true;
                vis[i]=false;
                if(len==0) return 0;//这里剪枝很重要，而且很经典。如果当前为0，即本次搜索失败，则一定会废弃一个static，则当前长度的分法肯定不成立。
                int last=st[i];
                while(last==st[i]) i++;
            }
        }
    }
    return false;
}
int main()
{

    while((scanf("%d",&n))&&(n!=0))
    {
        for(int i=0; i<=n; i++) vis[i]=false;
        int sum=0;
        cnt=0;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&st[i]);
            sum+=st[i];
        }
        sort(st,st+n,cmp);
        for(int i=st[0];i<=sum;i++)
        {

            if(sum%i==0)
            {
                //cout<<"fuck"<<endl;
                cnt=sum/i;
                l=i;
                if(dfs(0,0))
                {
                    printf("%d\n",l);
                    break;
                }
            }
        }
    }
}