记录编号	526603	评测结果	AAAAAAAAAA
题目名称	[POJ 1011] 木棍拼接	最终得分	100
用户昵称	云卷云书	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2019-01-27 18:34:09	内存使用	3.16 MiB

/*一、枚举总长度的所有约数L
能否拼成sum/L根长度为L的木棒

 
int a[]
5 2 1 5 2 1 5 2 1
bool v[]
正在拼第x根，拼了长度l */
#include<bits/stdc++.h>
using namespace std;
int a[70];
bool v[70];
int n, L, sum, m;
bool dfs(int x, int l, int last) {//last保证从大到小的顺序 只可能5 2 1 而不会搜2 5 1   1 2 5....  
	if (x > sum/L) return true;
	if (l == L) return dfs(x + 1, 0, 0);
	int failed = 0;
	for (int i = last + 1; i <= n; i++) {
		if (v[i]) continue;
		if (l + a[i] > L) continue; 
		if (a[i] == failed) continue;
		v[i] = true;
		if (dfs(x, l + a[i], i)) return true;
		failed = a[i];//这根木棍当前不能用 5 2 2 2 2 1 5和2不能组成的话后面的2都不用试了 
		v[i] = false;//回溯 
		if (l == 0) break;
		if (l + a[i] == L) break;
	}
	return false;
}

int main() {
	freopen("sticka.in","r",stdin);
	freopen("sticka.out","w",stdout);
	cin >> m;
	for (int i = 1; i <= m; i++) {
		int x;
		cin >> x;
		if (x <= 50) {
			a[++n] = x;
			sum += x;
		}
	}
	sort(a + 1, a + n + 1);
	reverse(a + 1, a + n + 1);//从大到小 
	for (L = 1; L <= sum; L++) {
		if (sum % L != 0) continue;//不是整数一定不能组成 
		memset(v, 0, sizeof(v));
		if (dfs(1, 0, 0)) break;
	}
	cout << L << endl;
}