5
一道值得做的深搜题目，彰显剪枝的强大。。。
题意就是：刚开始你有若干根长度为K的绳子（棍子、绳子都差不多），然后一个人把这些随机剪掉，
剪成n个短绳子，让你求这些短绳子组合成原来长度的绳子的最短长度。
也可说是：将n个数分成m堆，每一堆的和都相等为H，求H最小为多少。
题中有一些数字：
50：指剪后每一段绳子长度最大为50。
64：指剪后绳子数量最大为64。
还有注意，有可能有绳子根本就没有减。
比如：
5
1 2 3 4 5
最短的就是 1+4=2+3=5
初始就是3根长度为5的绳子，题目没要求求多少根，只求长度最小为多少。
这个题目做法，按照深搜步骤来就行，就是注意一下一些地方的剪枝，
第一次做有个剪枝我也没想到，但就因为那一个枝，让我 一直TLE，后来也是看别人代码看懂的。
主函数中那两个剪枝就不多说明，一看就懂。
主要是dfs函数中那三个if里的剪枝。
首先要明白，什么时候会回溯，就是当dfs进去搜索，发现没有符合的，才会回溯。
也就是说，只有当当前的数不符合的时候才会回溯出来。
第一条剪枝：
如果你剩余的长度和当前长度相等，就没有必要搜索，也就是说当你剩余长度为3，接着搜索3，发现不符合，就不需要搜索剩下能构成3的（比如2+1,1+1+1等）
第二条剪枝：（重要的）
意思是如果剩余的长度等于绳子总长度，而当前不符合，就不需要接着搜索。
也就是说，接下来搜索的长度就是绳子目标长度，而你当前长度根本用不上，那就肯定不符合了。
例子： 假设 要搜索目标长度为 7 ：绳长有 7 6 3 2 2.
假设 第一个7 搜索完，接下来搜索6 发现6没有1来配对，程序会接下来搜索 3 2 2，但很明显根本不需要搜索后面的，前面有一个用不上，后面就不需要再搜索了。
第三条剪枝：
如果当前长度的不满足，那么相同长度的就不需要再次去搜索
代码上也有一些解释：
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int n,maxx,sum,arr[70];
bool ispos,vis[70];
// 由大到小排序
bool cmp(int a,int b)
{
return a>b;
}
void dfs(int res,int js,int pos)
{
// 找到答案，返回
if(ispos==1) return;
// 如果所有都被选择 ispos置1，表示找到
if(js==n) {ispos=1;return;}
// 如果res=0 且并非所有都被选择，则继续将maxx dfs
if(res==0 && js<n) dfs(maxx,js,0);
int i;
for(i=pos;i<n;++i)
{
if(!ispos && !vis[i] && arr[i]<=res)
{
vis[i]=1;
dfs(res-arr[i],js+1,pos);
vis[i]=0;
// 这个去掉 +40MS
if(res==arr[i]) return;
// 这个去掉，TLE。。
if(res==maxx) return;
// 这个剪枝去掉了，+100MS
while(arr[i]==arr[i+1]) ++i;
}
}
}
int main()
{
int i;
while(cin>>n)
{
if(!n) break;
sum=0;
for(i=0;i<n;++i)
{
cin>>arr[i];
sum+=arr[i];
}
sort(arr,arr+n,cmp);
maxx=arr[0];
// 剪枝：如果最长的长度大于剩余所有长度和，则答案就是他们的和
//(这个去掉了也可以，耗时没有变化 = 。=，就是说不写也可以）
if(maxx>sum-maxx)
{
cout<<sum<<endl;
continue;
}
ispos=0;
while(!ispos)
{
// 剪枝： 如果所有长度总和 对 目标长度 取模不为0 ，则目标长度一定不是答案，这个必须有
// 这个如果去掉，耗时增多不说，对后面剪枝影响，会导致WA
while(sum%maxx!=0) {++maxx;}
memset(vis,0,sizeof(vis));
dfs(maxx,0,0);
if(ispos) break;
++maxx;
}
cout<<maxx<<endl;
}
return 0;
}
ACM-DFS之Sticks——hdu1455,布布扣,bubuko.com
原文：http://blog.csdn.net/lttree/article/details/23103573