#include <stdio.h>
#include <string.h>

int n,L[101],sum,max,Len,N;

bool got[5001],used[101];
int pre[5001];

/*
void Q_sort(int p,int r){
	if(p >= r) return ;
	int i = p - 1, j = r + 1, x = L[(p + r) / 2],t;
	while(true){
		do j-- while(L[j] > x);
		do i++ while(L[i] < x);
		if(i  >= j) break;
		t = L[i]; L[i] = L[j]; L[j] = t;
	}
	Q_sort(p,j);
	Q_sort(j+1,r);
}

*/

bool test(){
	memset(used,0,sizeof(used));

	int i,j,k;
	for(i=0; i<N; i++){		
		memset(got,0,sizeof(got)); got[0] = true;
		memset(pre,0,sizeof(got));
		for(j=0; j<n; j++)
			if (! used[j] ){
				for(k = L[j]; k <= Len; k++)
					if(got[k - L[j]]){
						pre[k] = j; got[k] = true; 
					}
				if(got[Len]) break;
			}	
		if(! got[Len] ) return 0;
		k = Len;
		while (k > 0){
			used[pre[k]] = true;
			k -= L[pre[k]];
		}
	}


	return true;
}

int main(){
	int i;

	while(scanf("%d",&n), n != 0){
		for(i = max = sum = 0; i<n; i++){
			scanf("%d",&L[i]); sum += L[i];
			if(L[i] > max) max = L[i];
		}

	//	Q_sort(0,n-1);
		for(N = n; N>0; N--)
			if(sum % N == 0){
				Len = sum / N; if(Len < max) continue;
				if(test()){
					printf("%d\n",Len); break;
				}
			}	
	}
	
	return 0;
}

• Re:最多是O(n^3 * L) 优化一下可以O(n^3) 欧这个程序有问题么？为什么会wa 呢？ (1377) lemongxr 2003-11-24 21:11:10
  • 请问。。 (59) lemongxr 2003-11-24 21:14:47