#include <stdio.h>

int  sticks[64] = {0} ;
int  stickCnt = 0 ;
char used[64] = {0} ;
int  len = 0 ;

void sort(int *sticks, int stickCnt)
{
	int i = 0, j = 0 ;
	int max = 0 ;
	int tmp = 0 ;

	for(i = 0; i < stickCnt - 1; i++)
	{
		max = i ;
		for(j = i+1; j < stickCnt; j++)
			if(sticks[j] > sticks[max])
				max = j ;
		
		if(i != max)
		{
			tmp = sticks[i] ;
			sticks[i] = sticks[max] ;
			sticks[max] = tmp ;
		}
	}
}

int dfs(int usedCnt, int curLen, int pos)
{
	int i = 0 ;

	if(curLen == len)
	{
		if(usedCnt == stickCnt)
			return 1 ;

		pos = 0 ;
		curLen = 0 ;
	}

	for(i = pos; i < stickCnt; i++)
	{
		if(used[i])
			continue ;

		if(curLen + sticks[i] > len)
			continue ;

		used[i] = 1 ;
		if(dfs(usedCnt + 1, curLen + sticks[i], i+1))
			return 1 ;
		used[i] = 0 ;

		if(0 == curLen)
			return 0 ;
		
		while((i < stickCnt) && (sticks[i+1] == sticks[i]))
			i++ ;
	}

	return 0 ;
}

int main(int argc, char *argv[])
{
	int  i = 0 ;
	int  sum = 0 ;

	while(scanf("%d", &stickCnt) && stickCnt)
	{
		sum = 0 ;
		for(i = 0; i < stickCnt; i++)
		{
			scanf("%d", &sticks[i]) ;
			sum += sticks[i] ;
		}

		sort(sticks, stickCnt) ;
		
		for(len = sticks[0]; len <= sum; len++)
		{
			if(sum % len == 0)
			{
				for(i = 0; i < stickCnt; i++)
					used[i] = 0 ;
				
				if(dfs(0, 0, 0))
					break ;
			}
		} 

		printf("%d\r\n", len) ;
	}

	return 0 ;
}

• Re:所有数据都能过, AC, 0ms!!! (1661) luminis 2016-04-16 18:46:26
  • Re:所有数据都能过, AC, 0ms!!! (0) Shadab420 2016-05-04 13:05:26