Sticks POJ - 1011

借鉴的这个人的

题解：
说一下三条剪枝函数,当运行到剪枝函数，可以理解为搜索失败了。
1.第一个剪枝：如果当前搜索a[i]时，发现因为a[i]的原因不能使木棍分成等长的几部分，当goal等于a[i]时，也就不需要在搜索了。
2，第二个剪枝：（引上面博客内容）假设 要搜索目标长度为 7 ：绳长有 7 6 3 2 2.
假设 第一个7 搜索完，接下来搜索6 发现6没有1来配对，程序会接下来搜索 3 2 2，但很明显根本不需要搜索后面的，前面有一个用不上，后面就不需要再搜索了。
3.第三个：如果a[i]搜索失败了，若a[i+1] == a[i]，就不用搜索了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

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

int n,a[70],mins,maxn,sum,vis[70];
bool flag;

void dfs(int goal,int num,int k)
{
    if(flag) return;
    if(num == n&&goal == 0) {flag = true; return;}
    if(goal == 0&&num<n) dfs(maxn,num,0);

    for(int i = k ; i < n ; i++)
    {
        if(!flag&&!vis[i]&&a[i]<=goal)
        {
            vis[i] = 1;
            dfs(goal-a[i],num+1,i+1);
            vis[i] = 0;

            //运行到这一步，一般可以理解为上面搜索失败了； 
            if(goal == a[i]) return;
            if(goal == maxn) return;
            while(a[i] == a[i+1]) i++;
        }
    }

}


int main()
{
    while(~scanf("%d",&n))
    {
        if(n == 0) break;
        sum = 0;
        flag = false;
        for(int i = 0 ; i < n ; i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        sort(a,a+n,cmp);        
        if(a[0]>sum-a[0])
        {
            cout<<sum<<endl;
            continue;
        }
        maxn = a[0];
        while(maxn<sum)
        {
            memset(vis,0,sizeof(vis));
            while(sum%maxn != 0) maxn++;//这里不能写成if； 
            dfs(maxn,0,0);
            if(flag) break;
            maxn++;
        }
        cout<<maxn<<endl;
    }
    return 0;



}