POJ 1011 Sticks DFS+很多剪枝 *

题目地址：http://poj.org/problem?id=1011

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cmath>
#include<cstring>
using namespace std;
int sticks[64+5],N,L,nLastStick;
bool used[64+5];
bool DFS(int R,int M)
{if(R==0&&M==0) return true;if(M==0) M=L;int nStartStick=0;if(M!=L) nStartStick=nLastStick+1;for(int i=nStartStick;i<N;i++){if(!used[i]&&sticks[i]<=M){if(i>0) {if(used[i-1]==false&&sticks[i]==sticks[i-1])continue;}used[i]=true; nLastStick=i;if(DFS(R-1,M-sticks[i])) return true;else {used[i]=0;if(sticks[i]==M||M==L) return false;}}}return false;
}
int main()
{while(scanf("%d",&N)&&N){int sum=0;for(int i=0;i<N;i++) scanf("%d",&sticks[i]),sum+=sticks[i];sort(sticks,sticks+N,greater<int>());for(L=sticks[0];L<=sum/2;L++){if(sum%L) continue;memset(used,0,sizeof(used));if(DFS(N,L)) {cout<<L<<endl; break;}}if(L>sum/2) cout<<sum<<endl;}return 0;
}