一、题目回顾
题目链接：Sticks
题意：给出一定数量的小木棒的长度，它是由等长的若干木棒随意砍断所得到的。对于给定的一组小木棒，请求出原始木棒的最小长度。
二、解题思路
- DFS+剪枝
- 本题剪枝不到一定火候将会TLE，只有完成一定的剪枝才能AC
本题，我将从我做这题的角度，将所思所想具体记录下来，详细的官版思想见我另一个题解。
首先，看main函数：
int main()
{
while(scanf("%d",&n) && n){
int sum=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum += a[i]; //记录现在所有木棒的长度之和
}
sort(a+1,a+1+n,cmp); //将数组a中的元素从大到小排列
int len;
flag = 0;
//原木棒长度一定大于等于现在的任何一支木棒（即大于等于最长的木棒）
//原木棒长度一定小于等于现在所有木棒的长度之和
for(len=a[1];len<=sum;len++){ //a[1]为最长木棒的长度
if(sum%len==0){ //原木棒的根数一定是个整数
memset(vis,0,sizeof(vis));
dfs(len,0,n); //假设原木棒长度为len，要拼的原木棒已拼成的长度为0，还有n根木棒
if(flag==1){ //已经拼成功，就退出，因为要原木棒尽可能短
break;
}
}
}
printf("%d
",len); //打印原木棒的长度
}
return 0;
}
做到这，我在思考，如果原木棒的根数大于1，那么在第一根原木棒拼完之后，我该如何确定第二根，第三根，…
【dfs形参的确定】
- len 假设的原木棒的长度
- now 现在拼的长度（在一根原木棒之内）
- num 剩下的小木棒数目
再看dfs的代码：
void dfs(int len,int now,int num) //预设的原木棒的长度 正在完成的木棒的长度 剩余的小木棒数量
{
if(num==0){
flag = 1;
return;
}
if(now==len) dfs(len,0,num);
for(int i=1;i<=n;i++){
if(!vis[i] && a[i]+now<=len){
vis[i] = 1;
dfs(len,a[i]+now,num-1);
if(flag==1) return;
vis[i] = 0;
if(a[i]==len-now || len==len-now) //此剪枝一开始没想到，超时
break;
}
}
}
形参中的三个数必须要在函数体内起到一定的作用。
回答上面的疑惑，我们不再判断是有几根，而是将num==0作为递归出口，当木棒没了，说明拼接成功了。而如果一根原木棒拼接完成，就继续深搜。
这里面一个剪枝一开始我没想到，一直TLE，具体解释见我另一个题解。
题外话：这种题目，自己实践慢慢领悟吧。
三、代码
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n,flag; int a[70]; bool vis[70]; bool cmp(const int a, const int b) { return a>b; } void dfs(int len,int now,int num) //预设的原木棒的长度 正在完成的木棒的长度 剩余的小木棒数量 { if(num==0){ flag = 1; return; } if(now==len) dfs(len,0,num); for(int i=1;i<=n;i++){ if(!vis[i] && a[i]+now<=len){ vis[i] = 1; dfs(len,a[i]+now,num-1); if(flag==1) return; vis[i] = 0; if(a[i]==len-now || len==len-now) //此剪枝一开始没想到，超时 break; } } } int main() { while(scanf("%d",&n) && n){ int sum=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); sum += a[i]; //记录现在所有木棒的长度之和 } sort(a+1,a+1+n,cmp); //将数组a中的元素从大到小排列 int len; flag = 0; //原木棒长度一定大于等于现在的任何一支木棒（即大于等于最长的木棒） //原木棒长度一定小于等于现在所有木棒的长度之和 for(len=a[1];len<=sum;len++){ //a[1]为最长木棒的长度 if(sum%len==0){ //原木棒的根数一定是个整数 memset(vis,0,sizeof(vis)); dfs(len,0,n); //假设原木棒长度为len，要拼的原木棒已拼成的长度为0，还有n根木棒 if(flag==1){ //已经拼成功，就退出，因为要原木棒尽可能短 break; } } } printf("%d ",len); //打印原木棒的长度 } return 0; }