//#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<functional>
using namespace std;
const int part = 4;
bool used[30] = {false};
int len[30];
int length;
int find1 = 0;
int n;
void dfs(int level,int curlen,int pth);
void fit(int pth)
{
	if(pth > 4)
	{
		find1 = 1;
	//	cout<<"yes\n";
		return ;
	}
	if(find1) return ;
	int i;
	for( i = 0 ; i <n ; i++)
	{
		if(!used[i])
			break;
	}
	used[i] = true;
	dfs(i,len[i],pth);
	used[i] = false;
}
void dfs(int level,int curlen,int pth)
{
	
	if(curlen == length )
	{
		fit(pth+1);
		return ;
	}
	if(level+1> n )
		return ;
	int i;

	for( i = level+1; i<n; i++)
	{
		if(find1) return ;
		if(!used[i])
		{
			if(curlen+len[i]<=length)
			{
				used[i] = true;
				dfs(i,curlen+len[i],pth);
				used[i] = false;
			}
		}
	}
}
int main()
{
	int testcase;
	int i,j;
	int total; 
//	cin>>testcase;
	scanf("%d",&testcase);
	for(i =1 ;i<=testcase; i++)
	{
		total = 0 ;
		find1 = 0;
	//	cin>>n;
		scanf("%d",&n);
		for(j = 0 ; j<n; j++)
		{
		//	cin>>len[j];
			scanf("%d",&len[j]);
			total +=len[j];
		}
	    if(total % 4 != 0)
			goto output;
		length = total/4;
		memset(used,false,sizeof(used));
		sort(len,len+n,greater<int>());
		//if don't add sort it cost 64 ms ,add it 0ms
		/*for(j = 0 ; j<n; j++)
		{//这个for循环出错了吗？
		//	printf("%d ",len[j]);
			if(len[j]>length)
				goto output;
			else if(len[j] == length)
			{
				if(n != 4)
					goto output;
			}
		}*/
		//when adding the cutoff method it go wa 
		
		fit(1);
output:
		if(find1 == 1) 
		//	cout<<"yes\n";
		   printf("yes\n");
		else //cout<<"no\n";
			printf("no\n");
	}
	return 1;
}

• 这个是常遇到的事，剪枝条件强过了wa, 删掉 ac or tle or wa (1923) Honest 2006-03-15 19:52:32
  • 用这个程序生成样例 ，怎么是 NO (192) cxf476 2006-04-17 15:09:00
    • 也许是sticks 太多了 ! (212) cxf476 2006-04-17 15:10:13
• 确实错了 (79) waterine 2006-11-15 20:55:37