4564564_tle.cpp

部分PKU上的源码

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

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

int now[65][65];//搜索状态
int finish[65];//搜索成功棍子数
int zero[64];//空的棍子数

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

bool ok;//是否成功

int stop;//test

void slove(int p)//p 搜索到第几个棍子
{
	if(ok) return;
	if(p>number) return;
	zero[p]=zero[p-1];
	for(int count=1;count<=n-zero[p]+1;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];
		}
		if(now[p][count]==0) zero[p]--;
		now[p][count]+=length[p];
		/*
		if(stop==10000) cin>>stop;
		system(   "cls"   );
		cout<<p;stop++;
		*/
		stop++;
		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()
{
	//
	//stop=0;
	//
	int first=true;
	while(1)
	{
		cin>>number;
		if(number==0) return 0;
		memset(length,0,sizeof(length));
		//memset(length,1,sizeof(length));
		//
		memset(now,0,sizeof(now));
		memset(zero,0,sizeof(zero));
		memset(finish,0,sizeof(finish));
		n=0;
		//max_length=1;
		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];
		}
		//
		//sum=number;
		//
		sort(length+1,length+1+number,bijiao);
		goal=max_length;
		while(1)
		{
			//
			stop=0;
			//
			ok=false;
			goal=get_next();
			if(goal==sum+1) break;
			n=sum/goal;
			zero[0]=n;
			slove(1);
			if(ok) 
			{
				if(first) cout<<goal;
				else cout<<endl<<goal;
				cout<<" "<<stop;
				break;
			}
		}
	}
}