![]()
思路
![]()
求解代码
// n: 小木棒总数, sum: 所有木棒总长度, targetL: 目标原始长度, numbers: 目标原始木棒根数privatestaticintn,sum,targetL,numbers;privatestaticInteger[]a;// 存储砍断后的小木棒长度publicstaticvoidmain(String[]args)throwsIOException{BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));PrintWriterout=newPrintWriter(newOutputStreamWriter(System.out));n=Integer.parseInt(br.readLine().trim());String[]s=br.readLine().trim().split("\\s+");a=newInteger[n];boolean[]used=newboolean[n];// 标记每根小木棒是否已被乔治使用sum=0;intmaxL=0;for(inti=0;i<n;i++){a[i]=Integer.parseInt(s[i]);sum+=a[i];maxL=Math.max(maxL,a[i]);// 原始长度至少要等于最长的那根小木棒}// 【剪枝优化 1】：降序排序。// 优先尝试长木棒。因为长木棒对位置要求更苛刻，如果它拼不通，能更早触发回溯。Arrays.sort(a,(x1,x2)->(x2-x1));// 枚举原始木棒可能的长度 targetL// 范围：从最长的那根开始，直到所有木棒的总和for(targetL=maxL;targetL<=sum;targetL++){// 【条件约束】：原始长度必须能被总长度整除，否则乔治不可能拼成同样长的木棒if(sum%targetL!=0){continue;}numbers=sum/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(completed==numbers){returntrue;}// 如果当前这根拼满了，开启下一根木棒的拼凑if(currentL==targetL){returndfs(completed+1,0,0,used);}for(inti=idx;i<n;i++){// 如果这根用过了，或者放进去就超过了目标长度，跳过if(used[i]||currentL+a[i]>targetL){continue;}// 【做选择】：尝试放这根木棒used[i]=true;if(dfs(completed,currentL+a[i],i+1,used)){returntrue;}// 【撤销选择】：刚才的尝试失败了，拿出来used[i]=false;// --- 核心剪枝策略 (极其关键) ---// 【剪枝优化 2】：首棒失败判定// 如果此时 currentL 为 0，说明我们正在尝试拼一根新木棒的第一部分。// 如果第一部分用这根最长的木棒都拼不出来，那后面更拼不出来了。// 【剪枝优化 3】：末棒失败判定// 如果加上这根木棒刚好填满了 targetL，但在后续递归中失败了，// 说明用这根刚好填满的方案不行，那么换用几根更碎的小木棒来填这个坑也肯定不行。if(currentL==0||currentL+a[i]==targetL){returnfalse;}// 【剪枝优化 4】：去重剪枝// 如果当前长度的木棒不行，那后面相同长度的木棒也肯定不行，直接跳过。while(i+1<n&&a[i+1].equals(a[i])){i++;}}returnfalse;}
