Acwing 167.木棒（剪枝必刷题）

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

为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。 数据范围 数据保证每一节木棍的长度均不大于 50。
题目链接：木棒

思路：可以直接去dfs，让木棒原始长度从小到大去dfs是否所有木棍都能拼成，并且原始长度一定可以整除总长度。这题需要考虑很多剪枝，不然会超时。

剪枝及优化：

1. 从小木棍最大的长度去尝试是否能拼成，因为每根木棍都是木棒砍下来的，木棒长度不可能比最长木棍还短。
2. 可以将所有木棍从大到小开始枚举，因为小木棍拼成木棒需要dfs拼接的木棍肯定多于大木棍dfs的木棍。
3. 木棒内木棍的编号递增，去除重复情况。例如对于编号1、2，3的两根木棍，换成3、1、2的顺序去拼，也是拼的同一种情况。
4. 若某一根木棍在拼某一根木棒时，拼接失败了，那么后面与它等长的木棍一定也不能拼接成功。
5. 若拼接某根木棒的第一根都失败了，直接返回false。
6. 若后面拼接某根失败了，一直往上返回，返回来拼接某一根的最后一根成功了，直接返回false，因为后面一定有不能拼接原始木棒的木棍。

代码（含注释）：

importjava.util.Scanner;importjava.util.Arrays;publicclassMain{staticint n, sum, len;// 木棍总数，总长度，原始长度staticint[] w;//存储各个木棍的长度staticboolean[] vis;//存储木棍是否被用了的数组publicstaticvoidmain(String[] args){Scanner sc =newScanner(System.in);while((n=sc.nextInt())!=0){
            w =newint[n]; 
            vis =newboolean[n];
            sum =0; len =1;for(int i =0; i < n; i++){
                w[i]= sc.nextInt();
                sum += w[i];
                len = w[i]> len ? w[i]: len;//找到木棍的最大长度}Arrays.sort(w);//从小到大排序reverse(w);//再反转数组，得到从大到小的顺序while(true){//让原始木棒长度从最长的木棍开始if(sum % len ==0&&dfs(0,0,0)){//原始长度一定能整除总长度System.out.println(len);//然后去dfs是否能拼成break;}
                len ++;//不能拼成就枚举下一个原始长度}}}/**
     * @param u 表示当前拼到第几根木棒了
     * @param cur 当前正在拼接的木棍总长度
     * @param start 从哪根木棍开始枚举的
     */publicstaticbooleandfs(int u,int cur,int start){if(u * len == sum)//若棒数 * 原始长度等于总长度，表示能拼成，返回truereturntrue;if(cur == len)//如果拼接的长度等于len，去拼下一根木棍returndfs(u+1,0,0);for(int i = start; i < n; i++){//从正在访问的木棍下一根开始枚举if(vis[i]|| cur + w[i]> len)continue;//若当前木棍已经被用了或拼接后大于len，就跳过
            
            vis[i]=true;//用当前木棍去拼if(dfs(u, cur + w[i], i +1))returntrue;
            vis[i]=false;//拼不成功，就又把它置为未使用的状态//这下面的所有语句就是if (dfs(u, cur + w[i], i + 1))返回false的情况if(cur ==0)returnfalse;//cur等于0，表示第一根小木棍都无法拼上//剪枝6，dfs后面的木棍返回的false，若当前木棍作为最后一根木棍拼上if(cur + w[i]== len)returnfalse;//后面也一定有拼不上的情况，因为上面拼接当前木棍返回的falseint j = i;while(j < n && w[j]== w[i]) j++;//当前木棍拼不上，后面等长的木棍也一定拼不上
            i = j -1;}returnfalse;}publicstaticvoidreverse(int[] a){//反转数组的方法int l =0, r = a.length-1;while(l<r){int temp = a[r];
            a[r--]= a[l];
            a[l++]= temp;}}}