1049.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1049 on 2005-11-06 at 19:17:36 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX = 64;

int stick[MAX], a[MAX];
bool used[MAX];
int n, m;

bool combin(int, int, int, int);

int main()
{
	int i, sum;

	while(scanf("%d", &n) == 1) {
		if(n == 0) {
			return 0;
		} else {
			sum = m = 0;
			for(i = 0; i < n; i++) {
				scanf("%d", &stick[m]);
				if(stick[m] <= 50) {
					sum += stick[m++];
				}
			}
			sort(stick, stick+m);
			a[0] = stick[0];
			for(i = 1; i < m; i++) {
				a[i] = a[i-1] + stick[i];
			}
			memset(used, false, sizeof(used));
			for(i = stick[m-1]; i < sum; i++) {
				if(sum % i == 0 && combin(0, i, m, sum)) {
					break;
				}
			}
			printf("%d\n", i);
		}
	}
	
	return 0;
}

bool combin(int cur, int l, int next, int sum)
{
	int i;
	bool app[MAX] = {false};
	if(sum == 0) {
		return true;
	}
	for(i = next-1; i >= 0; i--) {
		if(cur + a[i] < l) {
			return false;
		} else {
			if(!used[i] && !app[stick[i]] && cur + stick[i] <= l) {
				app[stick[i]] = true;
				used[i] = true;
				int p;
				if(cur + stick[i] == l) {
					p = m;
				} else {
					p = i;
				}
				if(combin((cur+stick[i])%l, l, p, sum-stick[i])) {
					return true;
				}
				used[i] = false;
				if(cur == 0) {
					return false;
				}
			}
		}
	}
	return false;
}