#include <cstdio>
#include <cstdlib>
#include <algorithm>
#pragma GCC optimize(2)                                          //O2优化
using namespace std;

inline int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
	while (c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
	return x*f;
}

const int MAXN=105;
int n,m,sum,len;
bool flag;
int stick[MAXN],next[MAXN];
bool used[MAXN];

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

inline void make_next()
{
	next[n]=n;
	for (int i=n-1;i>=1;i--)
	{
		if (stick[i]==stick[i+1])next[i]=next[i+1];
		else next[i]=i;
	}
}

inline int find(int l,int r,int x)
{
	int mid;
	while (l<r)
	{
		mid=(l+r)>>1;
		if (stick[mid]<=x)r=mid;
		else l=mid+1;
	}
	return l;
}

inline void dfs(int now,int rest,int last)
{
	if (rest==0)
	{
		if (now==1)
		{
			flag=true;
			return ;
		}
		int x=0;
		for (int i=1;i<=n;i++)
			if (!used[x=i])break;
		used[x]=true;
		dfs(now-1,len-stick[x],x);
		used[x]=false;
		if (flag)return ;
	}
	int l=find(last+1,n,rest);
	for (int i=l;i<=n;i++)
	{
		if (!used[i])
		{
			used[i]=true;
			dfs(now,rest-stick[i],i);
			used[i]=false;
			if (flag)return ;
			if (stick[i]==rest || len==rest)return ;
			i=next[i];
			if (i==n) return;
		}
	}
}

int main()
{
	while (true)
	{
		n=read();
		if (n==0)break;
		sum=0;flag=0;
		for (int i=1;i<=n;i++)
		{
			stick[i]=read();
			sum+=stick[i];
		}
		sort (stick+1,stick+n+1,cmp);
		make_next();
		for (int i=stick[1];i<=sum/2;i++)
		{
			if (sum%i==0)
			{
				len=i;
				used[1]=true;
				dfs(sum/i,i-stick[1],0);
				used[1]=false;
				if (flag)
				{
					printf("%d\n",len);
					goto end;
				}
			}
		}
		printf("%d\n",sum);
		end:continue;
	}
	return 0;
}

• Re:0ms 暴搜+剪枝+O2优化 (2042) royzxq 2019-05-01 18:13:04