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

yesiam大大,怎么剪枝啊?我还是TLE

Posted by Jin_j_y at 2005-04-24 09:58:32 on Problem 2362
In 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:
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