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