pku2362.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <stdlib.h>

int N;
int le[80], use[80], len, sum, no, found;

int cmp(const void *a, const void *b)
{
	return *(int *)b - *(int *)a;
}

void DFS(int remain, int nu, int last_id)
{
	int i;
	if (found)
	{
		return;
	}

	if (remain == 0)
	{
		if (nu == no - 1)
		{
			printf("yes\n");
			found = 1;
			return;
		}
		i = 0;
		while (use[i] == 1) i++;
		use[i] = 1;
		DFS(len - le[i], nu + 1, i);
		use[i] = 0;
		return;
	}
	else
	{
		if (last_id + 1 >= N)
		{
			return;
		}
		for (i = last_id + 1; i < N; i++)
		{
			if (use[i] == 0 && le[i] <= remain)
			{
				use[i] = 1;
				DFS(remain - le[i], nu, i);
				use[i] = 0;
				if (found || le[i] == remain)
				{
					return;
				}
			}
		}
	}
}

int main()
{
	int i, t;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &N);
		found = 0;
		for (i = 0, sum = 0; i < N; i++)
		{
			scanf("%d", &le[i]);
			sum += le[i];
		}

		if (sum % 4 != 0)
		{
			printf("no\n");
			continue;
		}

		qsort(le, N, sizeof(le[0]), cmp);

		for (i = 0; i < N; i++)
		{
			use[i] = 0;
		}
		no = 4;
		len = sum / 4;
		DFS(0, 0, 0);
		if (found == 0)
		{
			printf("no\n");
		}
	}
}