B23 DFS剪枝 小木棍

#include<bits/stdc++.h>
using namespace std;
int a[70], len, n, num;
bool v[70];
//cnt表示目前正在组建第几支长度为len的木棒
//s表示当前木棒的积累长度
//now表示当前考虑的原始木棒编号为now~n加入 
bool dfs(int cnt, int s, int now)
{
    if(cnt > num) return 1;
    if(s == len)  return dfs(cnt + 1, 0, 1);
    int fail = 0;//fail是灵魂，表示尝试失败的长度（有多根原始木棒长度相同时起作用） 
    for(int i = now; i <= n; i++)
    {
        if( v[i] == 1 && s + a[i] <= len && fail != a[i] )
        {
            v[i] = 0;
            if( dfs(cnt, s + a[i], i + 1) ) return 1;
            v[i] = 1;
            fail = a[i];
            if( s == 0 || s + a[i] == len ) return 0;
			//这里的剪枝也是秒，表示再也组建不了新len木棒 
        }
    }
    return 0;
}
int main()
{
    while(scanf("%d", &n) != EOF)
    {
        int sum = 0;
        for(int i = 1; i <= n; i++) {scanf("%d", &a[i]); sum += a[i];}
        sort(a + 1, a + 1 + n); reverse(a + 1, a + 1 + n);
        for(len = a[1]; len <= sum; len++)
        {
            if( sum % len != 0) continue;
            num = sum / len;
            memset(v, 1, sizeof(v));
            if(dfs(1, 0, 1) == True) break;
        }
        printf("%d\n", len); 
    }
     
    return 0;
}

B23 DFS剪枝 小木棍

#include<bits/stdc++.h>
using namespace std;
int a[70],len,n,num;
bool v[70];
//cnt表示目前正在组建第几支长度为len的木棒
//s表示当前木棒的积累长度
//now表示当前考虑的原始木棒编号为now~n加入 
bool dfs(int cnt,int s,int now)
{
    if(cnt>num) return 1;
    if(s==len)  return dfs(cnt+1,0,1);
    int fail=0;//fail是灵魂，表示尝试失败的长度（有多根原始木棒长度相同时起作用） 
    for(int i=now;i<=n;i++)
    {
        if( v[i]==1 && s+a[i]<=len && fail!=a[i] )
        {
            v[i]=0;
            if( dfs(cnt,s+a[i],i+1) ) return 1;
            v[i]=1;
            fail=a[i];
            if( s==0 || s+a[i]==len ) return 0;
			//这里的剪枝也是秒，表示再也组建不了新len木棒 
        }
    }
    return 0;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        int sum=0;
        for(int i=1;i<=n;i++) {scanf("%d",&a[i]);sum+=a[i];}
        sort(a+1,a+1+n);reverse(a+1,a+1+n);
        for(len=a[1];len<=sum;len++)
        {
            if( sum % len !=0) continue;
            num=sum/len;
            memset(v,1,sizeof(v));
            if(dfs(1,0,1)==True) break;
        }
        printf("%d\n",len); 
    }
     
    return 0;
}