//这题又折腾了两天 心好累
//poj、hdu数据极弱，找虐请上uvalive
题意：给出n个数，将其分为任意份，每份里的数字和为同一个值。求每份里数字和可能的最小值。
解法：dfs+剪枝
1.按降序排序，长的木棍应该优先被使用
2.一个木棍一旦确定就不应当改变，因为新得到的木棍不会更优
3.如果当前循环扫到的第一根木棍加不进去直接return false 因为可以在后面的循环里被搜到
4.如果前一根等长的没有被使用那么不进入循环
5.份数要能整除总长度才会检查是否为合法解
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<string> using namespace std; int n;
int crab[];
bool e[];
int MAX,tot_len,want_len; bool cmp(int a,int b){
return a>b;
} bool dfs(int now,int p,int l){
if (now*want_len==tot_len) return true;
for (int i=p;i<n;i++){
if (e[i] && !(i> && e[i-] && crab[i-]==crab[i])){//剪枝4
if (l-crab[i]==){
e[i]=false;
if (dfs(now+,,want_len)) return true;
e[i]=true;
return false;//剪枝2
}
if (l-crab[i]>){
e[i]=false;
if (dfs(now,i+,l-crab[i])) return true;
e[i]=true;
}
if (l==want_len) return false;//剪枝3
}
}
return false;
} int main(){
while (){
scanf("%d",&n);
if (n==) return ;
MAX=;
tot_len=;
for (int i=;i<n;i++){
scanf("%d",&crab[i]);
e[i]=;
tot_len+=crab[i];
MAX=max(MAX,crab[i]);
}
sort(crab,crab+n,cmp);//剪枝1
for (want_len=MAX;want_len<=tot_len;want_len++){
if ((tot_len%want_len==) && dfs(,,want_len)){//剪枝5
printf("%d\n",want_len);
break;
}
}
}
return ;
}
/*
4
4 3 2 1 9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
*/