附上我这个高效正确的可以过WOJ的,但又在这个莫名奇妙WA的快速算法.
PKU的数据肯定有问题, 在我的程序面前,管理员敢不敢公开这题的数据?
 
# include <iostream>
using namespace std;

const short maxsize = 65;
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;
} 

• 找到原因----> 现在Accepted了 (201) gzw_02 2008-05-22 19:47:44
  • Re:找到原因----> 现在Accepted了 (6) go4fun 2008-06-15 04:34:47
  • Re:找到原因----> 现在Accepted了 (229) HenrySnoopy 2008-08-04 10:48:43
  • Re:找到原因----> 现在Accepted了 (9) HenrySnoopy 2008-08-04 10:49:28
  • Re:找到原因----> 现在Accepted了 (20) PlayerZ 2008-08-07 00:30:42