思路求解代码// n: 小木棒总数, sum: 所有木棒总长度, targetL: 目标原始长度, numbers: 目标原始木棒根数privatestaticintn,sum,targetL,numbers;privatestaticInteger[]a;// 存储砍断后的小木棒长度publicstaticvoidmain(String[]args)throwsIOException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));PrintWriteroutnewPrintWriter(newOutputStreamWriter(System.out));nInteger.parseInt(br.readLine().trim());String[]sbr.readLine().trim().split(\\s);anewInteger[n];boolean[]usednewboolean[n];// 标记每根小木棒是否已被乔治使用sum0;intmaxL0;for(inti0;in;i){a[i]Integer.parseInt(s[i]);suma[i];maxLMath.max(maxL,a[i]);// 原始长度至少要等于最长的那根小木棒}// 【剪枝优化 1】降序排序。// 优先尝试长木棒。因为长木棒对位置要求更苛刻如果它拼不通能更早触发回溯。Arrays.sort(a,(x1,x2)-(x2-x1));// 枚举原始木棒可能的长度 targetL// 范围从最长的那根开始直到所有木棒的总和for(targetLmaxL;targetLsum;targetL){// 【条件约束】原始长度必须能被总长度整除否则乔治不可能拼成同样长的木棒if(sum%targetL!0){continue;}numberssum/targetL;// 计算在当前 targetL 下应该拼出多少根// 尝试拼凑初始已完成0根当前长度0从第0个小木棒开始找if(dfs(0,0,0,used)){out.println(targetL);// 找到第一个可行的最小长度即为答案break;}}out.flush();out.close();br.close();}/** * DFS 拼凑过程 * * param completed 已完整拼好的原始木棒根数 * param currentL 当前正在拼的那根原始木棒已经达到的长度 * param idx 为了避免重复组合从数组的哪一个下标开始挑选下一根小木棒 * param used 使用情况记录 */privatestaticbooleandfs(intcompleted,intcurrentL,intidx,boolean[]used){// 【递归出口】如果乔治拼好了所有原始木棒大功告成if(completednumbers){returntrue;}// 如果当前这根拼满了开启下一根木棒的拼凑if(currentLtargetL){returndfs(completed1,0,0,used);}for(intiidx;in;i){// 如果这根用过了或者放进去就超过了目标长度跳过if(used[i]||currentLa[i]targetL){continue;}// 【做选择】尝试放这根木棒used[i]true;if(dfs(completed,currentLa[i],i1,used)){returntrue;}// 【撤销选择】刚才的尝试失败了拿出来used[i]false;// --- 核心剪枝策略 (极其关键) ---// 【剪枝优化 2】首棒失败判定// 如果此时 currentL 为 0说明我们正在尝试拼一根新木棒的第一部分。// 如果第一部分用这根最长的木棒都拼不出来那后面更拼不出来了。// 【剪枝优化 3】末棒失败判定// 如果加上这根木棒刚好填满了 targetL但在后续递归中失败了// 说明用这根刚好填满的方案不行那么换用几根更碎的小木棒来填这个坑也肯定不行。if(currentL0||currentLa[i]targetL){returnfalse;}// 【剪枝优化 4】去重剪枝// 如果当前长度的木棒不行那后面相同长度的木棒也肯定不行直接跳过。while(i1na[i1].equals(a[i])){i;}}returnfalse;}