Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

ac了好爽啊!

Posted by chenxuan123456789 at 2012-09-09 19:56:19 on Problem 2362
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int n,num[30],len,f,flag[30];
int cmp(const void *_a,const void *_b)
{
	int *a=(int*)_a;
	int *b=(int*)_b;
	return *b-*a;
}
void dfs(int l,int s,int d)
{
	int i;
    if(d==3)
	{
		f=1;
		return;
	}
	if(l==0)
	dfs(len,0,d+1);
	for(i=s;i<n;i++)
	{
		if(num[i]<=l&&!flag[i])
		{
			flag[i]=1;
			dfs(l-num[i],i+1,d);
			flag[i]=0;
			while(i+1<n&&num[i]==num[i+1])i++;
		}
	}
}    
int main()
{
	int cases,i,sum;
	scanf("%d",&cases);
	while(cases--)
	{
		sum=0;
		scanf("%d",&n);
		for(i=0;i<n;i++)
		{
			scanf("%d",&num[i]);
			sum+=num[i];
		}
		if(sum%4)
		{
			printf("no\n");
			continue;
		}
		qsort(num,n,sizeof(num[0]),cmp);
		len=sum/4;
		f=0;
		memset(flag,0,sizeof(flag));
		dfs(len,0,0);
		if(f)
			printf("yes\n");
		else
			printf("no\n");
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator