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

Re:1011都不超时!这个偏偏超时

Posted by changchunteng at 2009-04-13 20:11:13 on Problem 2362
In Reply To:1011都不超时!这个偏偏超时 Posted by:changchunteng at 2009-04-13 20:10:59
> 我就将1011的程序改装了。
//http://162.105.81.212/JudgeOnline/problem?id=2362
//Square
//2009.4.13

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int arry[25];
bool a[25];


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

bool solve(int total,int lefttirks,int left,int len)
{
	if(lefttirks==0&&left==0)
		return true;
	if(left==0)
		left=len;

	for(int i=0;i<total;++i)
	{
		if(a[i]==true)
			continue;
		if(arry[i]>left)
			continue;
		a[i]=true;

		if(solve(total,lefttirks-1,left-arry[i],len))
			return true;
		a[i]=false;
		if(arry[i]==left||left==len)
			break;
	}
	return false;
}

void input()
{
	int test,n;

	//cin>>test;
	scanf("%d",&test);

	while(test--)
	{
		int sum=0;
	//	cin>>n;
		scanf("%d",&n);

		for(int i=0;i<n;++i)
		{
			a[i]=false;
			//cin>>arry[i];
			scanf("%d",&arry[i]);
			sum+=arry[i];
		}

		if(sum%4!=0||n<4)
		{
			cout<<"no"<<endl;
		}
		else 
		{
			qsort(arry,n,sizeof(int),cmp);
			sum/=4;
			//cout<<"arry[0]=="<<arry[0]<<" "<<sum<<endl;
			if(arry[0]>sum)
				printf("no\n");
			else 
			{
				if(solve(n,n,0,sum))
				{
					//cout<<"yes"<<endl;
					printf("yes\n");
				}
				else 
				{
					//cout<<"no"<<endl;
					printf("no\n");
				}
			}
		}
	}
}

int main()
{
	input();
	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