4473956_tle.cpp

部分PKU上的源码

#include<iostream>
#include<algorithm>
using namespace std;

int length[65];//棍子长度
int max_length;//最长棍子
int sum;//总长度

int now[65][65];//搜索状态
bool used[65];//是否已经使用
//int finish[65];//搜索成功棍子数
//int zero[64];//空的棍子数

int number;//棍子数
int n;//搜索棍子数
int goal;//目标棍子长度

bool ok;//是否成功

int stop;//test

bool get(int l,int begin)
{
	stop++;
	for(int count=begin;count<=number;count++)
	{
		if(!used[count]&&length[count]<=l) 
		{
			used[count]=true;
			if(length[count]==l){return true;}
			else if(get(l-length[count],count+1)) return true;
			//else return false;
		}
	}
	return false;
}
void slove(int p)//p 搜索到第几个棍子
{
	stop++;
	if(ok) return;
	if(p==n+1) {ok=true;return;}
	if(get(goal,1)) slove(p+1);
}
bool bijiao(int a,int b)
{return a>b;}
int get_next()
{
	int count;
	for(count=goal;count<=sum;count++)
	{
		if(sum%count==0) break;
	}
	return count;
}
int main()
{
	int first=true;
	while(1)
	{
		stop=0;
		//
		cin>>number;
		if(number==0) return 0;
		memset(length,0,sizeof(length));
		memset(now,0,sizeof(now));
		//memset(zero,0,sizeof(zero));
		//memset(finish,0,sizeof(finish));
		n=0;
		max_length=0;
		sum=0;
		for(int count=1;count<=number;count++)
		{	
			cin>>length[count];
			sum+=length[count];
			if(length[count]>max_length) max_length=length[count];
		}
		sort(length+1,length+1+number,bijiao);
		goal=max_length;
		while(1)
		{
			ok=false;
			goal=get_next();
			if(goal==sum+1) break;
			n=sum/goal;
			memset(used,false,sizeof(used));
			slove(1);
			if(ok) 
			{
				if(first) cout<<goal;
				else cout<<endl<<goal;
				//cout<<stop;
				break;
			}
		}
	}
}