| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
0ms 水过 贴代码#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator