4473605_tle.cpp

部分PKU上的源码

#include<iostream>
#include<algorithm>
using namespace std;
int length[64];//棍子长度
int max_length;//最长棍子
int sum;//总长度
int now[64][64];//搜索状态
int finish[64];//搜索成功棍子数
int number;//棍子数
int n;//搜索棍子数
int goal;//目标棍子长度
bool ok;//是否成功
int stop;
void slove(int p)//p 搜索到第几个棍子
{
	if(ok) return;
	if(p>number) return;
	for(int count=1;count<=n;count++)
	{
		if(now[p-1][count]+length[p]>goal) continue;
		if(now[p-1][count]+length[p]==goal)
		{
			finish[p]=finish[p-1]+1;
			if(finish[p]==n) {ok=true;return;}
		}
		else
		{
			finish[p]=finish[p-1];
		}
		for(int count2=1;count2<=n;count2++)
		{
			now[p][count2]=now[p-1][count2];
		}
		now[p][count]+=length[p];
		//
	//	if(stop==100) cin>>stop;
		//cout<<p;stop++;
		//
		slove(p+1);
	}
}
int get_next()
{
	int count;
	for(count=goal;count<=sum;count++)
	{
		if(sum%count==0) break;
	}
	return count;
}
int main()
{
	//
	stop=0;
	//
	int first=true;
	while(1)
	{
		cin>>number;
		if(number==0) return 0;
		memset(length,0,sizeof(length));
		memset(now,0,sizeof(now));
		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];
		}
		goal=max_length;
		while(1)
		{
			ok=false;
			goal=get_next();
			if(goal==sum+1) break;
			n=sum/goal;
			slove(1);
			if(ok) 
			{
				if(first) cout<<goal;
				else cout<<endl<<goal;
				break;
			}
		}
	}
}