sticks(木桩长度重装匹配).cpp

PKU第1011题源码

#include<iostream>
using namespace std;
int find(int* A,int v,int n){//n is the number of value in A that before the value v
	if(v==0)return 1;
	int s,f=0,i,sum=0;
	for(s=0;A[s]<=v && s<n;s++)sum+=A[s];
	s--;
//	cout<<"s="<<s<<" sum="<<sum<<endl;
    if(sum<v)return 0;
	else if(sum==v){
//		cout<<"s="<<s<<endl;
		for(i=0;i<=s;i++)A[i]=0;
		return 1;
	}
	for(i=s;i>=0;i--){
		if(A[i]!=0)f=find(A,v-A[i],i);
		else continue;
//		cout<<"f="<<f<<endl;
		if(f>0){
			A[i]=0;
			break;
		}
	}
	return f;
}
void swap(int A[],int i,int j){
	int temp=A[i];
	A[i]=A[j];
	A[j]=temp;
}
int partition(int A[],int l,int r,int& pivot){
	do{
		while(A[++l]<pivot);
		while((r!=0)&&(A[--r]>pivot));
		swap(A,l,r);
	}while(l<r);
	swap(A,l,r);
	return l;
}
void qsort(int A[],int i,int j){
	if(j<=i)return;
	int pivotindex=(i+j)/2;
    swap(A,pivotindex,j);
	int k=partition(A,i-1,j,A[j]);
    swap(A,k,j);
	qsort(A,i,k-1);
	qsort(A,k+1,j);
}
int main(){
	int n,i,A[64],B[64],sum,number,f,j,k;
	while(cin>>n){
			if(n==0)break;
		sum=0;
		for(i=0;i<n;i++){
			cin>>A[i];
			sum+=A[i];
		}
		qsort(A,0,n-1);
		i=A[n-1];
		f=0;
			number=-1;
		while(i<sum/2+1){
			f=0;
			number=-1;
			if(sum%i==0){
				for(j=0;j<n;j++)B[j]=A[j];
				number=sum/i;
				for(j=0,k=n;j<number && k>0;){
					if(B[k-1]!=0){
						int t;
						t=find(B,i-B[k-1],k-1);
						if(t==0)break;
						B[k-1]=0;
						f+=t;
						j++;
						for(t=0;t<n;t++)cout<<B[t]<<" ";
						cout<<endl;
					}
					k--;
				}
			}
			if(f==number){
				f=-1111;
				cout<<i<<endl;
				break;
			}
			i++;
		}
		if(f!=-1111)cout<<sum<<endl;
	}
	return 0;
}