本文主要是介绍hdu 1455 Sticks（DFS+剪枝），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：
hdu 1455
题目大意：
n个木棒，求原来木棒最短的长度（每个木棒等长且在数量上无限制，木棒可以未被折断过）。
思路：
DFS。三个参数，当前长度，当前遍历位置，当前已构成最短长度的个数。
注意剪枝。
从大到小排序，可以减少递归次数，不难理解。
详见代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=70;
int sumlen,anslen,num,k;
int sticks[MAXN];
bool vis[MAXN];
int n;bool cmp(int x,int y)
{return x>y;
}bool DFS(int ss,int ll,int pos)
{if(ss==num) return true;for(int i=pos;i<n;i++){if(vis[i]) continue;if(sticks[i]+ll==k){vis[i]=true;if(DFS(ss+1,0,0))return true;vis[i]=false;//勿忘}else if(sticks[i]+ll<k){vis[i]=true;if(DFS(ss,ll+sticks[i],i+1))return true;vis[i]=false;if(ll==0)return false;//ll==0说明遍历完一遍该树枝仍未用到，所以这种情况不存在while(sticks[i]==sticks[i+1])i++;//因为已排序，当当前木棒长度不行时，长度相等的木棒也不行，所以跳过}}return false;
}int main()
{while(scanf("%d",&n)!=EOF&&n){memset(vis,0,sizeof(vis));sumlen=0;for(int i=0;i<n;i++){scanf("%d",&sticks[i]);sumlen+=sticks[i];}sort(sticks,sticks+n,cmp);for(k=sticks[0];k<=sumlen;k++){if(sumlen%k!=0)continue;//木棒长度相等num=sumlen/k;//能构成多少个木棒if(DFS(0,0,0)){cout<<k<<endl;break;}}}return 0;
}
这篇关于hdu 1455 Sticks（DFS+剪枝）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
