#include <iostream>
#define MAX 100
using namespace std;

int stick[MAX];
int used[MAX];
int n, nLen;
int sumL, num;
int yes;

int cmp(const void *r1, const void *r2)
{
	return *(int *)r2 - *(int *)r1;
}



int dfs(int nl, int ni, int tn)//nl:now len;tn:now num;ni:search tx;
{
	int i;
	if(yes)return 1;
	if(tn == num){yes = 1; return 1;}        
	for(i=ni; i<n; i++)
	{
		if(!used[i])
		{
			if(nl+stick[i]<nLen)
			{
				now=stick[i];
				used[i]=1;
				if(dfs(nl+stick[i], i+1, tn))return 1;
				if(tn == num){yes = 1; return 1;}
				if(yes)return 1;
				used[i]=0;//??
				break;
			}
			else if(nl+stick[i]==nLen)
			{
				used[i]=1;
				if(dfs(0, 0, tn+1))return 1;
				if(tn == num){yes = 1; return 1;}
				if(yes)return 1;
				used[i]=0;
			}
		}
	}
	return 0;
}


int main()
{
	int i;
	while(scanf("%d", &n) && n)
	{
		sumL = 0;
		memset(stick, 0, sizeof(stick));
		//Input
		for(i=0; i<n; i++)
		{
			scanf("%d", &stick[i]);
			sumL += stick[i];
		}
		//Sort from big to small
		qsort(stick, n, sizeof(int), cmp);
 		for(i=stick[0]; i<sumL; i++)
		{
			yes = 0;
			if(sumL%i == 0)
			{
				memset(used, 0, sizeof(used));
				num = sumL/i;
				nLen = i;
				dfs(0, 0, 0);
				if(yes == 1)break;
			}
		}
		printf("%d\n", nLen);
	}
	return 0;
}

• Re:改了一遍。现在是TLE。。。。我崩溃了。。。。 (1508) ma3587 2009-05-13 13:04:31
• Re:改了一遍。现在是TLE。。。。我崩溃了。。。。 (1508) xu422 2009-06-13 12:14:10