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 )
		{

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