AcWing 167. 木棒
原题链接
中等
作者:
最后五分钟
,
2024-03-15 13:25:28
,
所有人可见
,
阅读 12
#include<bits/stdc++.h>
#define LL long long
#define x first
#define y second
#define de(x) cout<<#x<<" = "<<x<<" "
#define deg(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int N=70;
typedef pair<int,int> PII;
int w[N],s,len,st[N],n;
bool dfs(int u,int cnt,int idx)
{
if(u*len==s)return 1;
if(cnt==len)return dfs(u+1,0,1);
for(int i=idx;i<=n;i++)
{
if(st[i])continue;
int x=w[i];
if(cnt+x<=len)
{
st[i]=1;
if(dfs(u,cnt+x,i+1))return 1;
st[i]=0;
}
if(!cnt||cnt+x==len)return 0;
int j=i+1;
while(j<n&&w[j]==w[i])j++;
i=j-1;//跳过重复的棍
}
return 0;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
while(cin>>n,n)
{
s=len=0;
for(int i=1;i<=n;i++)
{
cin>>w[i];
s+=w[i];
len=max(len,w[i]);
}
sort(w+1,w+1+n,greater<int>());
memset(st,0,sizeof st);
while(1)
{
if(s%len==0&&dfs(0,0,1))
{
cout<<len<<endl;
break;
}
len++;
}
}
return 0;
}