| ||||||||||
| 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 | |||||||||
yesiam大大,怎么剪枝啊?我还是TLEIn Reply To:要剪支的 Posted by:yesiam at 2005-04-07 13:18:27 //#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int sticks[20];
int sums[20];
int x[4];
int a;
int DFS(int cur,int cen){
int i;
if(cen==3){
if(x[3]+sums[cur]==a)return 1;
return 0;
}
for(i=0;i<4;i++){
int temp=sticks[cur]+x[i];
if(temp>a)return 1;
x[i]=temp;
if(x[i]==a)cen++;
if(DFS(cur+1,cen)==0)return 0;
if(x[i]==a)cen--;
x[i]-=sticks[cur];
}
}
int main(){
//ifstream cin("in.txt");
int csn;cin>>csn;
int i,sum,temp;
while(csn--){
cin>>n;
sum=0;
for(i=0;i<n;i++){
cin>>temp;
sticks[i]=temp;
sum+=temp;
}
if(sum%4||n<4){cout<<"no"<<endl;continue;}
a=sum/4;
sort(sticks,sticks+n);
i=n-1;sums[i]=sticks[i];
while(sums[i]<=a){i--;sums[i]=sums[i+1]+sticks[i];}
for(i=0;i<4;i++)x[i]=0;
if(DFS(0,0)==0)cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator