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

0ms 水过 贴代码

Posted by szy532164656 at 2012-12-09 19:57:21 on Problem 2362
#include <iostream>
#include <algorithm>

using namespace std;

int number;
int stick[10001] = {0};
bool ifVisit[10001] = {false};
int length = 0;

bool cmp( int a, int b )
{
	if ( a > b )
		return true;
	else
		return false;
}

bool dfs( int tempLength, int tempTimes, int tempIndex )
{
	int now=-1;
	for ( int i = tempIndex  ; i < number ; i ++ )
	{
		if (  stick[i] == now && tempLength != length )
			continue;
		if ( !ifVisit[i] && stick[i] <= tempLength )
		{
			now = stick[i];
			ifVisit[i] = true;
			if ( tempLength == stick[i] )
			{
				if ( tempTimes - 1 == 1 )
					return true;
				else if ( dfs( length, tempTimes-1, 0 ) )
					return true;
				else
				{
					ifVisit[i] = false;
					return false;
				}
			}
			else if ( tempLength > stick[i] )
			{
				if ( dfs(tempLength-stick[i], tempTimes, i) )
					return true;
				else
				{
					ifVisit[i] = false;
					if ( tempLength == length )
						return false;
				}
			}
		}
	}
	return false;
}

int main()
{
	int testCase;
	cin>>testCase;
	for ( int testCount = 0 ; testCount < testCase ; testCount ++ )
	{
		cin>>number;
		int sum = 0;
		for ( int i = 0 ; i < number ; i ++ )
			ifVisit[i] = false;
		for ( int i = 0 ; i < number ; i ++ )
		{
			cin>>stick[i];
			sum += stick[i];
		}
		if ( sum % 4 != 0 || number < 4 )
			cout<<"no"<<endl;
		else
		{
			length = sum/4;
			sort( stick, stick+number, cmp );
			if ( stick[0] > length )
				cout<<"no"<<endl;
			else if ( dfs(length, 4, 0 ) )
				cout<<"yes"<<endl;
			else
				cout<<"no"<<endl;
		}
	}
}

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