用计数排序的思想多好呢！而且省得排序，省得某剪枝中前一个和后一个一样的情况（两根棍子等长，前一个失败后一个直接跳过），省得再用一个数组存某根棍是否被占用（还得从头扫描），何乐而不为？

代码：
#include <stdio.h>
#include <stdlib.h>
#define N 55
int stick[N],t[N],a;

// 深搜（ 还需的长度, 之后的最长长度, 倒数第几根, 剩余棍子总长）;
//返回 1 为深搜失败, 0 为成功.
int dfs( int len, int k, int rem, int left) {
    if( rem==0 )   return 0;
    if( len==0 )   return dfs(a,a,rem-1,left);
   	if( k>=N )     k=N-1;
    if( k>len )    k=len;
    if( t[k]==0 )
        while( k>0 && t[--k]==0 );
    if( k==0 )	return 1;
    if( len==a ) {
        t[k]--;
        if( dfs(len-k,k,rem,left)==0 ) return 0;
        t[k]++;
        return 1;
    }
    if( k<=len ) {
        for( ; k>0 && left>=len ; left-= t[k]*k,k--)
			if( t[k]>0 ) {
				t[k]--;
                if( dfs(len-k,k,rem,left)==0 ) return 0;
				t[k]++;
			}
		return 1;
    }/* Core above */
}

int main()
{
    int i,k,n,sum;
    while( scanf("%d",&n), n ) {
        memset( stick, 0, N*sizeof(int) );
        for( sum=k=0; n--; ) {
            scanf("%d",&i);
            stick[i]++;
            if( i>k ) k=i;
            sum +=i;
        }
		for( a=k; a<=sum; a++ )
            if( sum%a==0 ) {
                for( i=0; i<N; i++)
                    t[i]=stick[i];
				if( dfs(a,a,sum/a,sum)==0 )
                    break;
            }
		printf("%d\n",a);
    }
    system("PAUSE");
    return 0;
}


这个代码瞬出 64的那个BT用例：
64
40 40 30 35 35 26 15 40 40 40 40 40 40 40 40 40 40 40 40 40 40 
40 40 43 42 42 41 10 4 40 40 40 40 40 40 40 40 40 40 40 40 40 
40 25 39 46 40 10 4 40 40 37 18 17 16 15 40 40 40 40 40 40 40 40


最后表达一下对那些直接复制粘贴本段代码之人的强烈鄙视。

• 确实，我自己过的那个测这个BT数据时用了9秒，谢谢分享~ (0) catcher_wang 2009-10-21 10:58:00
• 这个算法有一个小Bug！！！ (53) Zenomyth 2009-10-22 22:27:01
  • 我再添一个BUG (26) liushijian 2010-01-16 18:54:56
• Re:何必都那么复杂呢？晒晒我的代码，计数排序 (10) 0809114213 2010-08-16 01:31:32
  • Re:二B (14) 0809114213 2010-08-16 01:32:06
  • Re: 装逼遭雷劈 操你妈的 (14) 0809114213 2010-08-16 01:32:31
• Re:何必都那么复杂呢？晒晒我的代码，计数排序 (1780) jiexianzhu 2010-08-29 17:58:38