题解 P1120 【小木棍 ［数据加强版］】
这一道题一看数据，很明显的剪枝+深搜。
主要思路：枚举最终小木棍的长度 ，搜索能不能拼出K根但是会超时……于是就需要剪枝。
几个注意点：
-
原话：管理员注：要把超过
50 的长度自觉过滤掉，坑了很多人了！ -
剪枝要剪到极致。
剪枝点：
-
如果第
i 个棍子不能拼成假设的长度，则和第i 个棍子相同长度的棍子也是不可能的，所以可以直接跳过去的！（很明显） -
将所有题目给的棍子的长度按照从大到小的顺序排列，然后按照此顺序进行深搜。（为的是给后边的小木棍更多的机会，减小搜索树的大小）
-
替换第
i 根棍子的第一根木棒是没用的，替换第i 根的最后一根棒子也是没用的（这一根不行，将其换成两根小木棍的和也是没用的） -
只需枚举总和的因子。（因为是分成等长的段数）
-
如果某次拼接选择长度为
S 的木棒，导致最终失败，则在同一位置尝试下一根木棒时，要跳过所有长度为S 的木棒。（很显然）（这一点我没有用，很可惜，如果有了这个，时间会更快。）
献上代码：
/*剪枝点会在代码后用【x】标出*/
#include<bits/stdc++.h>
using namespace std;
int n,mg[100],tmp,top=1,tt=0;
/*mg是木棍，tmp是转化用变量，top是木棍个数+1（左闭右开）
tt是总长
*/
bool vis[100];//判断该木棍是否用过
int cmp(int a,int b){
return a>b;//比较函数
}
bool dfs(int num/*剩几根*/,int len/*大棍长*/,int rest/*剩余长*/,int last/*上一根棍子*/){
if((rest==0)&&(num==0)) return 1;//放完了
if(num==0) return 0;//放完了但还有剩余
if(rest==0) {//一根分完了
rest=len;//切到下一根
last= 0;
}//开始新的一根
for(int i=last+1;i<top;i++){//从上一个长度往后搜，也是剪枝
if(vis[i]) continue;//使用过了，直接跳过
if(mg[i]>rest){//剪枝【1】
while(mg[i]==mg[i+1]&&i<top) i++;//切到下一根不同长的木棍
continue;
}
vis[i]=1;//摆上
if(dfs(num-1,len,rest-mg[i],i)) return 1;//如果它后边的木棍可以摆成，那么它就可以
vis[i]=0;//拿掉
if((mg[i]==rest)||(len==rest)) break;//剪枝【3】
while(mg[i]==mg[i+1]&&i<top) i++;//同上
}
return 0;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&tmp);
if(tmp<=50)//按照管理员的话说，筛一下
mg[top++]=tmp,tt+=tmp;
}
sort(mg+1,mg+top,cmp);//降序排序
for(int i=mg[1];i<=tt;i++){
if(tt%i!=0) continue;//剪枝点【4】
if(dfs(top-1,i,i,0)){//找到最小长
/*
因为可行木棍长不一定连续，
所以要从1来寻找最小值。
*/
printf("%d",i);
return 0;
}
}
return 0;
}