計蒜客 正方形 dfs剪枝

要點：
記得剪枝呀！！！當知足條件時候設置flag = true, 當其餘分支發現flag = true時,結束該分枝。ios

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
int n;
int p[5];//定義4個桶 
int sum = 0;
int len;
int A[10010];
int t;
bool flag = false; 
bool cmp(int a,int b){
	return a>b;
}
void dfs(int index){
	if(index>n+1||flag==true){
		return;
	}
	if(index==n+1&&p[1]==p[2]&&p[2]==p[3]&&p[3]==p[4]){
		flag =true;
		return;
	}
	//木棍扔第1個桶
	if(p[1]+A[index]<=len){
		p[1] +=A[index];
		dfs(index+1);
		p[1] -=A[index];	
	}
	//木棍扔第2個桶
	if(p[2]+A[index]<=len){
		p[2] +=A[index];
		dfs(index+1);
		p[2] -=A[index];
	}
	//木棍扔第3個桶
	if(p[3]+A[index]<=len){
		p[3] +=A[index];
		dfs(index+1);
		p[3] -=A[index];
	}
	//木棍扔第4個桶
	if(p[4]+A[index]<=len){
		p[4] +=A[index];
		dfs(index+1);
		p[4] -=A[index];	
	}
}
int main(){
	memset(p,0,sizeof(p));
	//freopen("in.txt","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>A[i];
		sum += A[i];
	}
	if(sum%4!=0){
		flag = false;
		cout<<"No\n";
	}
	else{
		len = sum/4;
		sort(A+1,A+n+1,cmp);
		dfs(1);
		if(flag){
			cout<<"Yes\n";
		}
		else{
			cout<<"No\n";
		}	
	}
	return 0;
}