洛谷 UVA307小木棍题解

题目是这样描述的： 乔治拿来一组等长的木棒，将它们随机的砍掉，得到若干根小木棍，并使每一节小棍的长度都不超过50个单位。然后他又想把这些木棍拼接起来，恢复到裁剪前的状态，但他忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度，每一节木棍的长度都用大于零的整数表示。输入包含多组数据，每组数据包括两行。第一行是一个不超过64的整数，表示砍断之后具有多少节木棍。第二行是截断以后，所得到的各节木棍的长度。在最后一组数据之后。是一个零。

对于每组数据，分别输出原始木棒的可能最小长度。

看一看这道题，绝对是一道DFS啊，只不过需要进行多重剪枝罢了，还是一道很经典的题了

来看看代码吧：

#include<iostream>#include<bits/stdc++.h>

using namespace std;

int a[66],nd=0,lmark,ans,sum,n;

bool vis[66];

bool cmp(int x,int y) {

return x>y;

}

bool dfs(int num,int len){

if(num==0&&len==0)

return 1;

if(len==0)len=nd;

int mark=1;

if(len!=nd)

mark=lmark+1;

for(int i=mark; i<=mark; i++)

if(vis[i]==0&&a[i]<=len) {

if(i>1&&vis[i-1]==0&&a[i]==a[i-1])

continue;

vis[i]=1;

lmark=i;

if(dfs(num-1,len-a[i]))

return 1;

else {

vis[i]=0;//回溯

if(len==a[i]||len==nd)

return 0;

}

}

return 0;

}

int main() {

while(scanf("%d",&n),n) {

ans=sum=0;

for(int i=1; i<=n; i++) {

scanf("%d",a+i);

sum+=a[i];

}

sort(a+1,a+n+1,cmp);//排序

for(int i=a[1]; i<=sum/2; i++) {

if(sum%i)continue;

memset(vis,0,sizeof(vis));

lmark=1;

nd=i;

if(dfs(n,i)) {

ans=i;

break;

}

}

if(ans)printf("%d\n",ans);

//else printf("%d\n",sum);

}

return 0;

}