题目链接

小木棍

题目思路

dfs的思想需要学习，努力剪枝减小时间复杂度
当第一个木棍尝试dfs无法拼成后，直接break
当最后一个尝试dfs无法拼成后，直接break
a[i]不行的话，等于a[i]的也不行

代码实现

#include<bits/stdc++.h>
using namespace std;
const int Max=100;
int n,nmax,sum,a[Max],vis[Max];
bool cmp(int a,int b)
{
    return a>b;
}
bool dfs(int num,int len,int rest,int now)
{
    if(num==0&&rest==0)    return 1;
    if(rest==0&&num!=0)
    {
        rest=len;
        now=1;
    }
    for(int i=now;i<=n;i++)
    {
        if(vis[i]||a[i]>rest)    continue;
        vis[i]=1;
        if(dfs(num-1,len,rest-a[i],i))    return 1;
        vis[i]=0;
        if((a[i]==rest)||(len==rest))    break;
        while(a[i]==a[i+1])    i++;
    }
    return 0;
}
int main()
{
    cin>>n;
    nmax=sum=0;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    sort(a+1,a+n+1,cmp);
    int num=n;
    for(int ii=a[1];ii<=sum;ii++)
    {
        if(sum%ii!=0) continue;
        if(dfs(num,ii,ii,1))
        {
            cout<<ii<<endl;
            return 0;
        }
    }
    return 0;
}