全部的测试数据我都通过,还AC过了WOJ..
不知道在这里为什么WA..

附程序.

# include <iostream>
using namespace std;

const short maxsize = 64;
short sticks[maxsize];
bool  isused[maxsize]; 
short gl;  //当前应找合并的木棍数
short n; //当前木棍总数
short partlen; //当前每段应该合成的长度
int comp(const void * a,const void *b){
	short *ca = (short*)a;
	short *cb = (short*)b;
	return *cb - *ca;
}
bool findstick(short index, short step, short clen){
	// clen --- 累加长度 <= partlen
	// step --- 找到的木棍数  step为gl-1时结束
	// index --- 当前要取的木棍
	int k;
	if( step==gl-1) return true; 
	isused[index]=1;
    if(clen==partlen){
		if(step>0&&!isused[step-1]){
			isused[index]=0;
			return false;
		}
		clen=0;
		step++;
	}
	
	for(short i=step;i<n;i++){
		
		
		if(!isused[i]){
			if(partlen-clen>sticks[i]){
				if(!findstick(i,step,clen+sticks[i])){
					k=i;
					while(sticks[++i]==sticks[k]);
					i--;
				}   else{
					return true;
				}
			}
			else if(partlen-clen==sticks[i]){    
				return findstick(i,step,clen+sticks[i]);
			}
		}//isused
		
	}//for
	isused[index]=0;
	return false;
}
int main(){
	while(cin>>n){
		
		if(!n) break;
		int i=0;
		int sum=0;
		int maxlen = 0;
		while(i<n){
			cin>>sticks[i];
			sum+=sticks[i];
			if(maxlen<sticks[i]) maxlen=sticks[i];
			i++;
		}
		//对sticks[0..n-1]降序排序
		qsort(sticks,n,sizeof(short),comp);
		// maxlen到sum的长度k，使得sum%k=0的最小的k值
		for(int k=maxlen;k<=sum;k++){
			if(sum%k==0) {
				for(i=0;i<n;i++){
					isused[i]=0;
				}
				gl = sum/k;
				partlen = k;
				if(findstick(0, 0,sticks[0])){
					cout<<k<<endl;
					break;
				}
			}
		}
	}
	return 1;
} 

• Re:不AC的兄弟姐妹们,看看下面的数组是不是过不去 (49) gzw_02 2008-05-21 23:19:03