题解 P1120 【小木棍 ［数据加强版］】
这就是一道DFS(大法师)
不要想多了
多想想剪枝！
附上题解，程序内有很详尽的注释(针对poj1011的，当然也有针对luogu的代码，附在里面了)
/*
POJ 1011
木棒
**************************
木棒
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 156283
Accepted: 37378
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
**************************
luogu上的题目，可能会有长度>50的木棍存在，所以你们自己过滤下qwq
我就针对这道POJ上的题目写个题解
思路差不多嘛qwq
管理员不给过就熊你哈VwV
*/
#include<bits/stdc++.h>
using namespace std;
int n,lmark,ans,sum;
int nd;//当前枚举到的木棍长度
int a[66];//记录木棍长度
bool vis[66];//记录木棍有没有被用过
bool cmp(int x,int y) {//排序比较规则，将木棍从大到小排序
return x>y;
}
bool dfs(int num,int len) {//num表示还有num根可以用,len表示还有len的长度就构造成1根完整的了
if(num==0&&len==0)//如果木棍全部用完然后又构造好了木棍
//由我们前面是计算除法，所以当num==0时，木棍的根数定然是最多的AwA
return 1;
if(len==0)len=nd;//构造完1根了，就再来一根
int mark=1;//记录循环开始点
if(len!=nd)mark=lmark+1;//如果不是一根全新的开始，就把mark（循环开始点）记为lmark+1(前面非重复木棍的位置)
for(int i=mark; i<=n; i++)//剪枝，从前面非重复的位置开始循环 (枚举与当前木棍（已构成）进行匹配的木棍)
if(vis[i]==0&&a[i]<=len) {//vis数组记录这个木棍有没有被用过
if(i>1&&vis[i-1]==0&&a[i]==a[i-1])//剪枝；当出现重复木棍时，直接跳过
//可以证明，在重复木棍中任取一根，不影响答案最终结果
/*
An example
Input
6
1 1 1 2 2 2
Output
3
可以见得，取第1根和取第2根和取第3根和后面的长度为2的木棍进行匹配，是不影响程序最终结果的
重复的只计算第一根
那么可以减少计算量
由于我们已经排过序了
那么判断重复就简单了
*/
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;//len==a[i]说明当前木棍是被剩余的
//len==nd是指当前木棍 无法被匹配（即上面的dfs(num-1,len-a[i])无法被触发）
//那么当前答案肯定不是一种可行的方案
}
}
return 0;
}
int main() {
while(scanf("%d",&n),n) { //针对POJ的哦
//如果是luogu上的话
//应该介样子写
//scanf("%d",&n);
ans=sum=0;
for(int i=1; i<=n; i++) {
scanf("%d",a+i);
sum+=a[i];//sum累计总长度，为后面的剪枝做好铺垫
}//也是针对POJ的和蔼数据
//对于luogu，你应该这样子写
/*
int cnt=n,n=0;
for(int i=1;i<=cnt;i++)
{
int x;
scanf("%d",&x);
if(x<=50)a[++n]=x;
}
*/
sort(a+1,a+n+1,cmp);//排序，为去重做好铺垫
for(int i=a[1]; i<=sum/2; i++) {//剪枝;每根木棍的长度只可能sum>=x>=min{a},且不可能在sum{a}/2-sum{a}之间
//即若在sum{a}/2-sum{a} 之间时
//定然会触发sun%i>0的条件
//减少计算量qwq
if(sum%i)continue;//剪枝；如果木棍的总长度无法整除当前枚举的长度
//说明无论如何都无法构成完整的根
memset(vis,0,sizeof(vis));//把标记数组清空
lmark=1;
nd=i;//记录下来枚举到的长度（我懒得开全局变量了2333）
if(dfs(n,i)) {
ans=i;
break;//如果搜到了，因为我们是从小到大循环，如果找到了，那么这个解定然是最优解
//直接记录下ans，就可以闪人了
}
}
if(ans)printf("%d\n",ans);//如果ans有被更新过（即找到了比所有的凑成1根更好的答案），那么输出更好的答案
else printf("%d\n",sum);//不然就把所有拼到一起
}
return 0;//完结撒fafa
}其实蓝书（信息学奥赛一本通【提高篇】）上面有更多的剪枝
但是似乎有些剪枝奇奇怪怪
是错的呢qwq
好惹，就到这里啦。
我是分割线