zp1909_p_wf.cpp

来自「浙江大学acm在线判题器代码集。 本人在浙大acm判题器上的所有代码（心血） 」· C++ 代码 · 共 81 行

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 20
int n;
int Stick[MAX], locate[MAX];
int left[4];
int ave, maxstick;

void Input()
{
	scanf("%d", &n);
	ave = 0;
	maxstick = 0;
	int i;
	for (i = 0; i < n; ++i)
	{
		scanf("%d", &Stick[i]);
		ave += Stick[i];
		if ( maxstick < Stick[i] ) 
			maxstick = Stick[i];
	}
}

int compare(const void * p1, const void * p2 )
{
	if ((*(int *)p1) < (*(int *)p2))
		return 1;
	else
		return -1;
}


bool CanFormSquare(int st)
{
	if (st >= n) return true;
	int i;
	for (i = locate[st] + 1; i < 4; ++i)
	{
		if ( Stick[st] <= left[i] )
		{
			left[i] -= Stick[st];
			locate[st] = i;
			if ( CanFormSquare(st+1) )  return true;
			left[i] += Stick[st];
			if (left[i] == ave) break;
		}
	}
	locate[st] = -1;
	return false;
}

int main(int argc, char *argv[])
{
	int Test;
	scanf("%d", &Test);
	while(Test --)
    {
		Input();
		qsort(Stick, n, sizeof(int), compare);
		memset(locate, -1, sizeof(locate));

		if (ave % 4 > 0 || maxstick > ave / 4)
		{
			printf("no\n");
			continue;
		}
		ave /= 4;
		left[0] = ave - Stick[0];
		locate[0] = 0;
		left[1] = left[2] = left[3] = ave;

		if (CanFormSquare(1))
			printf("yes\n");
		else 
			printf("no\n");
	}
	return 0;
}