1956.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

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

const int MAX = 32;

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

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

int main()
{
	int T, t, i;
	int sum;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &n);
		sum = 0;
		for(i = 0; i < n; i++) {
			scanf("%d", &stick[i]);
			sum += stick[i];
		}
		a[0] = stick[0];
		for(i = 1; i < n; i++) {
			a[i] = a[i-1] + stick[i];
		}
		memset(used, false, sizeof(used));
		if(sum % 4 != 0) {
			printf("no\n");
		} else {
			sort(stick, stick+n);
			sum /= 4;
			if(combin(0, sum, n, 4*sum)) {
				printf("yes\n");
			} else {
				printf("no\n");
			}
		}
	}
	
	return 0;
}

bool combin(int cur, int l, int next, int sum)
{
	int i;
	if(sum == 0) {
		return true;
	} else {
		for(i = next-1; i >= 0; i--) {
			if(cur + a[i] < l) {
				return false;
			} else {
				if(!used[i] && cur + stick[i] <= l) {
					used[i] = true;
					int p;
					if(cur + stick[i] == l) {
						p = n;
					} 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;
}