Jorbe's Blog

刚看到这道题时，努力在找规律，试图通过归纳法总结出一些规律。想法是好的，而且通过归纳法也确实找出了一些需要剪枝的地方，但还是没找到一个可行的算法，最后参考了一大牛的解题报告，才想到应该用DFS来解(经验严重不足:-( )。
假设归纳：假设这些小stick可以组成(n-1)根长度相同的大stick，则剩余的小stick也一定可以组成第n根长度相同的大stick。
这个归纳假设，显然是对的，因为大stick长度相同，只要可以组成(n-1)根，剩下的小stick长度之和一定为一根大stick的长度，所有假设成立。因此，有这个归纳假设，我们可以把m_len (可以组成的大stick最小长度,后面程序中有介绍)的取值区间缩小为[max{part[]},sum-m_len]，其中max{part[]}表示输入的小棍中最大长度，sum表示所有输入小棍长度之和。
代码中还给出了，其他一些需要注意的剪枝地方。

/*
*题目出处：http://poj.org/problem?id=1011   Sticks
*解题思路:深度优先搜索加剪枝
*几个需要注意的剪枝地方：
*1、诺能在(maxlen~sum-m_len)区间找到m_len，则m_len就是(maxlen,sum)区间上的m_len
*2、诺对某根长度为part[i]的stick进行深度优先搜索得不到结果时，就不用再对后面长度为part[i]的stick进行深度优先搜索了
*3、诺以part[s]为搜索起点，搜索完所有part[]后都不能构造长度为m_len的stick时，则跳出循环不用再往下搜索
*status: Accepted
*author：Jorbe
*date:  2013.11.26
*/
#include<iostream>
#include<algorithm>

using namespace std;

int cmp(const int &a,const int &b)
{
	if(a>b)
		return 1;
	else
		return 0;
}

int n; //输入木棒根数

bool dfs(int* part,bool* visted,int len,int m_len,int s,int num) //len:当前正在组合的part[]长度 m_len:原来sticks的最小长度
{                                                                //s:part[]的搜索起点 num:已用的part[i]数量
	if(num==n)
		return true;
	int is_equal=-1;    //判断part[]是否等长
	for(int i=s;i<n;i++)
	{ 
		if(visted[i]||part[i]==is_equal)  //诺part[i]已被用过，或前面已对长度为part[i]进行了dfs，则继续执行下一次循环
			continue;
		visted[i]=true;
		if(len+part[i]<m_len)
		{
			if(dfs(part,visted,len+part[i],m_len,i,num+1))
				return true;
			else
				is_equal=part[i];        //以后诺有相同长度的part[]则跳过(相同长度的part[]只需搜索一次)，直接进入下一次循环
		}
		else if(len+part[i]==m_len)
		{
			if(dfs(part,visted,0,m_len,0,num+1))
				return true;
			else 
				is_equal=part[i];
		}
		visted[i]=false;  //诺前面两种情况都不能组成一根长度为m_len的stick，则重新把part[i]设置为未使用过
		if(len==0)        //len==0,说明以part[s]为搜索起点，所有组合都不能满足组成长度为m_len的stick，跳出循环不用再往下搜索了
			break;
	}
	return false;
}

int main()
{
	int part[64];
	bool visted[64];
	while(1)
	{
		int sum=0;  //part数组和
		int m_len;  //sticks的最小长度
		cin>>n;
		if(n==0) break;
		for(int i=0;i<n;i++)
		{
			cin>>part[i];
			if(part[i]<=0||part[i]>50) return 0;
			sum+=part[i];
			visted[i]=false;
		}

		sort(part,part+n,cmp); //对part数组按降序排序
		int maxlen=part[0];
		bool flag=false;  //判断是否能在(maxlen~sum-m_len)区间找到m_len，诺不能则m_len=sum
		for(m_len=maxlen;m_len<=sum-m_len;m_len++) //剪枝：诺能在(maxlen~sum-m_len)区间找到m_len,则此m_len也是(maxlen~sum)上的最短长度stick
		{
			if(sum%m_len==0 && dfs(part,visted,0,m_len,0,0))
			{
				cout<<m_len<<endl;
				flag=true;
				break;
			}
		}
		if(!flag)            //诺在(maxlen~sum-m_len)区间不能找到m_len，则输出part[]数组之和
			cout<<sum<<endl;
	}
	return 0;
}

• ← 求最近点对算法
• GCJ Bribe the Prisoners 解题报告 →