记录编号	186259	评测结果	AAAAAAAAAA
题目名称	[POJ 1011] 木棍拼接	最终得分	100
用户昵称	Skyo	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2015-09-12 11:51:39	内存使用	0.29 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n, a[65], sum, side, num;
bool used[65];
bool cmp(int a, int b){
	return a > b;
}

bool s(int edge, int sum, int last){
	if(sum == side) edge++, sum = last = 0;
	if(edge == num-1) return 1;
	for(int i = last+1; i <= n; i++){
		if(used[i] || a[i] + sum > side) continue;
		if(a[i] == a[i-1] && !used[i-1]) continue;
		used[i] = 1;
		if(s(edge, sum+a[i], i)) return 1;
		used[i] = 0;
		if(!sum) break;
	}
	return 0;
}

int main()
{
	freopen("sticka.in", "r", stdin);
	freopen("sticka.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d", a+i);
		if(a[i] > 50) a[i] = 0;
		sum += a[i];
	}
	sort(a+1, a+n+1, cmp);
	side = a[1]-1;
	while(1){
		side++;
		if(sum % side) continue;
		num = sum / side;
		if(s(0, 0, 0)) {
			printf("%d\n", side);
			break;	
		}
	}	
}