AcWing 167. 木棒
原题链接
中等
作者:
十六
,
2021-01-20 19:16:15
,
所有人可见
,
阅读 263
#include<bits/stdc++.h>
using namespace std;
const int MAX = 70;
int n, sum, ans;
int a[MAX];
bool vis[MAX];
bool dfs(int num, int cnt, int pos){
if(num==n) return true;
if(cnt==0) cnt = ans, pos = 0;
for(int i=pos; i<n; i++){
if(a[i]<=cnt && !vis[i]){
vis[i] = true;
if(dfs(num+1, cnt-a[i], i+1)) return true;
vis[i] = false;
//cnt==ans 说明a[i]这根木棍不能作为木棒的开头
//cnt-a[i]==0 说明这根木棍不能作为木棒的结尾
//表明当前的ans是不合法的
if(cnt==ans || cnt-a[i]==0) return false;
int j = i;
while(j<n && a[j]==a[i]) j++;
i = j-1;
}
}
return false;
}
int main(){
while(scanf("%d", &n), n){
sum = 0;
memset(vis, false, sizeof vis);
for(int i=0; i<n; i++){
scanf("%d", &a[i]);
sum += a[i];
}
sort(a, a+n, greater<int>());
for(int i=a[0]; i<=sum; i++){
if(sum%i) continue;
ans = i;
if(dfs(0, ans, 0)) break;
}
cout<< ans<< endl;
}
return 0;
}