poj1011木棒 dfs

2017年03月22日 13点热度 0人点赞 0条评论
木棒
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 143464   Accepted: 33889

Description

乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序,帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。

Input

输入包含多组数据,每组数据包括两行。第一行是一个不超过64的整数,表示砍断之后共有多少节木棍。第二行是截断以后,所得到的各节木棍的长度。在最后一组数据之后,是一个零。

Output

为每组数据,分别输出原始木棒的可能最小长度,每组数据占一行。

Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output

6

5

//dfs+剪枝,有两层搜索的过程
//可以加入,就加入,如果错误就回溯,又是连续的,就少了个dfs不加的情况 
#include
#include
#include
bool cmp(int b,int c){return b>c;}
using namespace std;
int vis[100],n,a[100],s,tt,num;
bool dfs(int ss,int len,int pos){
	//ss为当前的和,len为当前达到目标长度的个数,pos为当前的位置
	if(len==num) return true;
	for(int i=pos;i>n&&n){
		s=0;
	for(int i=0;i>a[i];
		s+=a[i];
	}
	sort(a,a+n,cmp);
	for(tt=a[0];tt<=s;tt++)
		if(s%tt==0)
		if(num=s/tt,memset(vis,0,sizeof(vis)),dfs(0,0,0))
		{
			cout<
未经允许不得转载!poj1011木棒 dfs

update

纸上得来终觉浅, 绝知此事须躬行。