>    1 一开始只注意到了那个第一次搜索用最长的木棍，失败了的话证明它无论怎么摆放都不能 组成原始木棍，这个很好理解。超时了，自己在网上找了找，后来改成了
> if(left == target_len || arr[i] == left )
> 		{
> 			break;
> 		}
> 网上的解释是：使用当前木棍的时候，能拼出一个长度是L的木棍，但是后面的过程失败了。这两种情况都直接返回失败，不用做尝试。这个也不难理解，因为当前木棍始终是要放到某个目标木棍里面去的。
> 自己看的不是很懂，希望能有人解释下。
>     2 自己能优化的都优化了，从TLE到63MS到13MS。但是测试那组BT64的数据时电脑貌似就不懂了！！！！！！！！太让我诧异了。
> 小弟贴下自己的代码，由于费了九牛二虎之力，没有思路的或者对DFS不是很了解的朋友可以参考下
> #include<iostream>
> using namespace std;
> 
> bool used[100];
> int arr[100];
> int sum;
> 
> //基本思路：一个一个木棍开始填充，注意几个剪枝条件
> bool dfs(int unused, int left, int target_len)
> {
> 	//递归边界条件
> 	if(unused == 0 && left == 0)
> 	{
> 		return true;
> 	}
> 	//一开始情况，将搜索的剩余长度设置成为目标长度
> 	if(left == 0)
> 	{
> 		left = target_len;
> 	}	
> 	int i;
> 	for(i=0; i<sum; i++)
> 	{
> 		//如果这个短棍用过，当然不需要再搜索
> 		if(used[i])
> 		{
> 			continue;
> 		}
> 		//如果这个短棍长度目前已经长于被填充的剩余长度，当然不符合条件
> 		if(arr[i] > left)
> 		{
> 			continue;
> 		}
> 		//是用这个木棍
> 		used[i]=true;
> 		//在用去了这个小木棍后能够使得全部剩余木棍组合完毕，当然搜索成功
> 		if(dfs(unused-1, left-arr[i], target_len))
> 		{
> 			return true;
> 		}
> 		//使用了这个小木棍后搜索不成功，进行回溯。还原条件
> 		used[i]=false;
> 		//以下内容是一个很有用的剪枝条件：长度相同的木棍不重复搜索
> 		//比如：5 2 2 1 .... 第一个2搜索完毕后是失败的，那么第二个2当然不用再和5组合了
> 		while(arr[i] == arr[i+1])
> 		{
> 			i++;
> 		}
> 		//以下内容是一个及其重要的剪枝条件
> 		//1 left == target_len 说明当前第一个开始被测试的最长的那个小木棍加入后整体不成功
> 		//2 arr[i] == left 说明加入arr[i]后成功组合好了一个原始木棍，但是整体不成功
> 		//共同原因：dfs是递归测试的，当前木棍始终是要放到某个目标木棍里面去的。而且题目要求用完
> 		//          所有木棍
> 		if(left == target_len || arr[i] == left )
> 		{
			break;
		}
	}
	return false;
}

int main()
{
	int sum_len, max_len;
	int i,j;
	while(cin >> sum)
	{
		if(sum == 0)
		{
			break;
		}
		//记录最大值和总长度，从最大值开始搜索，每次加一，并且要求sum_len%i==0
		sum_len = 0;
		max_len = 0;
		for(i = 0; i < sum; i++)
		{
			used[i]=false;
			cin >> arr[i];
			
			if(max_len < arr[i])
			{
				max_len = arr[i];
			}

			sum_len += arr[i];
		}
		//sort 倒序，感觉从大到小组合的好一些
		int temp;
		for(i = 1 ; i < sum; i++)
		{
			for(j = 0; j < sum-i; j++)
			{
				if(arr[j] < arr[j+1])
				{
					temp = arr[j+1];
					arr[j+1] = arr[j];
					arr[j] = temp;
				}
			}
		}
		for(i=max_len; i<=sum_len; i++)
		{
			if(sum_len%i == 0)
			{
				if(dfs(sum, 0, i))
				{
					break;
				}
			}
		}
		cout << i << endl;
	}
	return 0;
}

• Re:两点疑问，希望有大牛解答下！小弟感激涕零 (171) cyb88 2010-02-02 23:51:33