C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 384K, 提交时间: 2020-07-19 17:57:00

#include <bits/stdc++.h>

using namespace std;
int a[100],vis[100],n,num,len;
bool dfs(int sticks,int rest,int last)
{
    if(sticks==num+1) return true;
    if(rest==0) return dfs(sticks+1,len,0);
    int fail=-1;
    for(int i=last+1;i<=n;i++)
        if(!vis[i]&&rest>=a[i]&&a[i]!=fail)
        {
            vis[i]=true;
            if(dfs(sticks,rest-a[i],i)) return true;
            vis[i]=false;
            fail=a[i];
        if(rest==len||rest==a[i]) return false;
        }
    return false;
}
int main()
{
    while(cin>>n&&n)
    {
        int sum=0,m=0,x;
        for(int i=1;i<=n;i++)
            {
                cin>>x;
                if(x<=50) {a[++m]=x;sum+=x;}
            }
            n=m;
        sort(a+1,a+n+1,greater<int>());
        memset(vis,0,sizeof(vis));
        for( len=a[1];len<=sum;len++)
            {
                if(sum%len) continue;
                num=sum/len;
                if(dfs(1,len,0)) break;
            }
            cout<<len<<endl;
    }
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 5ms, 内存消耗: 404K, 提交时间: 2023-03-11 21:10:00

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int a[N],cnt,len,n;
int v[N];
bool dfs(int p,int c,int lst)
{
    if(p==cnt) return true;
    if(c==len) return dfs(p+1,0,0);
    int fl=0;
    for(int i=lst;i<n;++i){
        if(!v[i]&&c+a[i]<=len&&fl!=a[i]){
            v[i]=1;
            if(dfs(p,c+a[i],i+1)) return true;
            fl=a[i];
            v[i]=0;
            if(c==0||c+a[i]==len) return false;
        }
    }
    return false;
}
int main()
{
    while(cin>>n&&n){
        int s=0;
        for(int i=0;i<n;++i){
            cin>>a[i];
            if(a[i]>50){
                --i;--n;
                continue;
            }
            s+=a[i];
        }
        sort(a,a+n);
        reverse(a,a+n);
        for(len=1;len<=s;++len){
            if(s%len) continue;
            cnt=s/len;
            memset(v,0,sizeof v);
            if(dfs(0,0,0)) break;
        }
        cout<<len<<endl;
    }
    return 0;
}

C++ 解法, 执行用时: 15ms, 内存消耗: 384K, 提交时间: 2021-06-15 21:58:51

#include<bits/stdc++.h>
using namespace std;
int a[110],v[110],n,tot,cnt,l;
int dfs(int stick,int cab)
{
	if(stick>cnt) return 1;
	if(cab==l) return dfs(stick+1,0);
	int fail=0;
	for(int i=1;i<=tot;i++)
	{
		if(!v[i]&&cab+a[i]<=l&&fail!=a[i])
		{
			v[i]=1;
			if(dfs(stick,cab+a[i])) return 1;
			v[i]=0;
			fail=a[i];
			if(cab==0||cab+a[i]==l) return 0;
		}
	}
	return 0;
}
int main()
{
	while(~scanf("%d",&n),n)
	{
		tot=0;int val=0,s=0;memset(v,0,sizeof(v));
		for(int i=1;i<=n;i++)
		{
			int x;scanf("%d",&x);
			if(x>50) continue;
			a[++tot]=x;
			s+=x;
			val=max(val,x);
		}
		sort(a+1,a+1+tot);
		reverse(a+1,a+1+tot);
		for( l=val;l<s;l++)
		{
			if(s%l) continue;
			cnt=s/l;
			if(dfs(1,0)) break;
		}
		printf("%d\n",l);
	}
}