题目

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 50
个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序，帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

输入格式

输入包含多组数据，每组数据包括两行。

第一行是一个不超过 64的整数，表示砍断之后共有多少节木棍。

第二行是截断以后，所得到的各节木棍的长度。

在最后一组数据之后，是一个零。

输出格式

为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

数据范围

数据保证每一节木棍的长度均不大于 50。

• 输入样例：

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

• 输出样例：

6
5

题解

import java.io.*;
import java.util.*;

/**
 * @author akuya
 * @create 2024-03-20-15:08
 */
public class Main {
    static int N=65;
    static int n;
    //木棍长度
    static int[] w=new int[N];
    //去重
    static boolean[] st=new boolean[N];
    //木棍总长与木棍的最大长度
    static int sum,len;
    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
        while(true){
            n=Integer.parseInt(br.readLine());
            if(n==0){
                break;
            }
            sum=len=0;
            String t[]=br.readLine().split(" ");
            for(int i=0;i<n;i++){
                w[i]=Integer.parseInt(t[i]);
                sum+=w[i];
                len=Math.max(len,w[i]);
            }

			//第一次裁枝，先从长木棍开始选
            Arrays.sort(w,0,n);
            for(int i=0;i<n/2;i++){
                int temp=w[i];
                w[i]=w[n-i-1];
                w[n-i-1]=temp;
            }
		
            Arrays.fill(st,0,n,false);
            while (true) {
            //第二次剪，筛选因数
                if(sum%len==0&&dfs(0,0,0)){
                    pw.println(len);
                    break;
                }
                len++;
            }

        }
        br.close();
        pw.flush();
        pw.close();

    }
    public static boolean dfs(int u,int cur,int start){
        if(u*len==sum) return true;
        if(cur ==len) return  dfs(u+1,0,0);

        for(int i=start;i<n;i++){
            if(st[i]) continue;
            if(cur+w[i]<=len){
                st[i]=true;
                if(dfs(u,cur+w[i],i+1)) return true;
                st[i] =false;
            }


			//第三次减枝第一步
            if(cur==0 || cur+w[i]==len) return false;

			//第二步当前长度失败，则跳过所有单签长度
            int j=i+1;
            while(j<n&&w[i]==w[j])j++;
            i=j-1;
        }
        return false;
    }
}

思路

这道题是有一较有难度的暴力搜索，看似代码短而简单，少减一条枝干直接TLE。具体剪枝分为三步。
第一步，让数值逆序排序，先排长数值，会让深搜更快达到裁枝标准，从而降低深搜深度。
第二步，只搜索总长的因数，这个好理解。
第三步分为三个部分
1.如果当前使用当前树枝得到的结果是最后无法达成目标，那么所有的该长度树枝都在这一步跳过。
2.每个第一次用的树枝，在作为拼凑木棍的第一根树枝时，该情况下如果最后无法达成目标，则该长度的分组无论如何无法成立，直接返回false。
3.每个第一次用的树枝，在作为拼凑木棍的最后根树枝时，该情况下如果最后无法达成目标，则该长度的分组无论如何无法成立，直接返回false。

满足以上三步裁枝才能不TLE，以上裁枝都可以用数学数学证明，这里就不说证明了。