sticks(dfs，强剪枝).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <functional>
#include <algorithm>
using namespace std;

int stick[70], n, seg_len, sum;
bool use[70];

bool
dfs(int seg, int len, int pos)
{
	if(seg == 0) {
		return true;
	}

	int i,j,st,sl,sp;
	for(i=pos;i<n;i++) {
		if(!use[i] && len >= stick[i]) {
			sl = len - stick[i];
			st = seg;
			sp = i+1;
			
			if(sl == 0) {
				sl = seg_len;
				st = seg -1;
				sp = 0;
			}

			use[i] = true;
			if( dfs(st, sl, sp) ) {
				return true;
			}
			use[i] = false;
			//if the seg_len can't build, mustn't be answer
			if(sl == seg_len || len == seg_len) {
				return false;
			}
			//ignore the same length
			while(stick[i] == stick[i+1] && i+1 < n) {
				i ++;
			}
		}
	}
	return false;
}

int
main()
{
	int i,j,k;
	while(scanf("%d", &n),n) {
		sum = 0;
		j = 0;
		for(i=0;i<n;i++) {
			scanf("%d", &stick[j]);
			if(stick[j] <= 50) {
				sum += stick[j];
				j ++;
			}
		}
		n = j;
		if(n == 0) {
			printf("0\n");
			continue;
		}
		sort(stick,stick+n,greater<int>());
		for(i=n;i>0;i--) {
			if(sum % i == 0) {
				seg_len = sum / i;
				if(seg_len < stick[0]) {
					continue;
				}
				memset(use,0,sizeof(use));
				if( dfs(i,seg_len,0) ) {
					break;
				}
			}
		}
		printf("%d\n", seg_len);
	}
}