pku 1011 填充棍子.txt

ACM资料大集合

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;
#define PB push_back
//PKU 1011 填充棍子

#define NMAX 5000
#define INFI 99999999

int xnum;//切成段后的短棍子数目
int dnum;//原先棍子数目
int dlen;//原先棍子长度
bool used[NMAX];
int len[NMAX];

bool search(int k,int nowlen,int st)
{//第k段原棍子，已填充nowlen长度，现在用第st根短棍
 //思路：将第k根棍子填充满后，填充第k+1根
	int i;
	if(k==dnum+1) return true;
	for(i=st;i<=xnum;i++)
	{
		if(used[i]==false)
		{
			if(len[i]+nowlen<dlen)
			{	//可以放入，但是长度不够
				used[i]=true;
				if(search(k,nowlen+len[i],i+1)==true) return true;
				used[i]=false;
				if(st==1) break;//第一根短棍（最长的）都不能用，以后的情况也不能用，立刻返回false
			}
			else if(len[i]+nowlen==dlen)
			{	//长度刚好，去填充下一根棍子
				used[i]=true;
				if(search(k+1,0,1)==true) return true;
				used[i]=false;
				break;//？？？不能把所有的原棍填满，直接返回false
			}
		}
	}
	return false;
}

bool cmp(int a,int b)
{
	return a>b;
}

void solve()
{
	int i,sum=0;
	sort(len+1,len+1+xnum,cmp);
	for(i=1;i<=xnum;i++) used[i]=false;
	for(i=1;i<=xnum;i++) sum+=len[i];
	for(i=len[1];i<=sum;i++)
	{
		if(sum%i==0)
		{
			dnum=sum/i;
			dlen=i;
			if(search(1,0,1)==true) 
			{
				printf("%d\n",i);
				return;
			}
		}	
	}
}

int main()
{
	int i;
	scanf("%d",&xnum);
	while(xnum!=0)
	{
		for(i=1;i<=xnum;i++)
			scanf("%d",&len[i]);
		solve();
		scanf("%d",&xnum);
	}
	return 0;
}