Sticks
- 描述
- George took sticks of the same length and cut them randomly until all parts became at most 5 units long. Now he wants to return sticks
to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers
greater than zero.- 输入
- The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line
of the file contains zero. - 输出
- The output should contains the smallest possible length of original sticks, one per line.
- 样例输入
-
9 5 2 1 5 2 1 5 2 1 4 1 2 3 4 0
- 样例输出
-
6 5
题目的意思就是：一些同样长的木棒，被随意的砍断，直到最长的不超过5，然后求初始时，这些木棒最小的长度。即将这些木棒拼凑成一些等长的木棒，并使这个长度最小。
DFS+剪枝
这里主要是有很多剪枝的技巧。
思路：（参考：http://www.cnblogs.com/newpanderking/archive/2011/10/03/2198648.html）
设所有木棍的总长度为 Sum, 最终的答案（长度）是 L。
1. 首先要明白， Sum一定要能被 L 整除。
2. L 一定 大于等于 题目给出的最长的木棍的长度 Max。由上述两点，我们想到，可以从 Max 开始递增地枚举 L, 直到成功地拼出 Sum/L 支长度为 L 的木棍。
搜索种的剪枝技巧：
3. 将输入的输入从大到小排序，这么做是因为一支长度为 K 的完整木棍，总比几支短的小木棍拼成的要好。
形象一些：
如果我要拼 2 支长为8的木棍，第一支木棍我拼成 5 + 3然后拼第二支木棍但是失败了，而我手中还有长为 2 和 1 的木棍，我可以用 5 + 2 + 1 拼好第一支，再尝试拼第二支，注定会失败，仔细想一想，就会发现这样做没意义。 所以当发现5+3=8，但还是失败的时候，就不需要再往下搜索了。
4. 相同长度的木棍不要搜索多次， 比如：我手中有一些木棍, 其中有 2 根长为 4 的木棍， 当前搜索状态是 5+4+.... 进行深搜后不成功，故我没必要用另一个 4 在进行 5+4+...
5. 将开始搜索一支长为 L 的木棍时，我们总是以当前最长的未被使用的 木棍开始，如果搜索不成功，那么以比它短的开始那么也一定不能取得全局的成功。因为每一支题目给出的木棍都要被用到。
如果，有
5
5 4 4 3 2
想拼成长为 6 的木棍，那么从 5 开始， 但是显然没有能与 5一起拼成 6 的，那么我就没必要去尝试从 4 开始的，因为最终 5 一定会被遗弃。在拼第 2 3 ... 支木棍时，一样。
#include
<iostream>02.#include
<algorithm>03.#include
<string.h>04.using namespace std;05. 06.#define
MAXS 6607. 08.//切断后的所有木棒的长度，木棒的访问标志，所有木棒的长度和，原始木棒数，原始木棒长度，现在木棒数09.int stick[MAXS],vis[MAXS],sum,num,len,n;10. 11.bool compare(int a,int b)12.{13.return a>b;14.}15. 16.//已组合木棒数，待组木棒的已有长度，开始搜索的下一个木棒17.bool dfs(int x,int l,int k)18.{19.if(x==num)return true;20.for(int i=k;i<n;i++)21.{22.if(vis[i])continue;23.if(l+stick[i]==len)24.{25.vis[i]=1;26.if(dfs(x+1,0,0))return true;27.vis[i]=0;28.return false;29.}30.else if(l+stick[i]<len)31.{32.vis[i]=1;33.if(dfs(x,l+stick[i],i+1))return true;34.vis[i]=0;35.if(l==0)return false;36.while(stick[i]==stick[i+1])i++;37.}38.}39.return false;40.}41. 42.int main()43.{44.while(cin>>n&&n)45.{46.sum=0;47.for(int i=0;i<n;i++)48.{49.cin>>stick[i];50.sum+=stick[i];51.}52.memset(vis,0,sizeof(vis));53.sort(stick,stick+n,compare);54.for(len=stick[0];len<=sum;len++)55.{56.if(sum%len==0)57.{58.num=sum/len;59.if(dfs(0,0,0))60.{61.cout<<len<<endl;62.break;63.}64.}65.}66.}67.return 0;68.}