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