mostshadow

用户名：most2022

访问量：2064

签　名：

等　　级
排　　名	4284
经　　验	1729
参赛次数	0
文章发表	7
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

题目 2356: 信息学奥赛一本通T1445-平板涂色（JAVA）
浏览：203

题目 1462: 蓝桥杯基础练习VIP-Huffuman树（JAVA+优先队列）
浏览：99

题解 1523: 蓝桥杯算法提高VIP-打水问题（JAVA+贪心）
浏览：177

你可能喜欢

信息学奥赛一本通T1442-小木棍（JAVA）

　　作者: mostshadow　　　　发表时间：2022-01-27 09:59:22 浏览：680　|　评论：0　

原题链接：信息学奥赛一本通T1442-小木棍

#### 注意事项：记得对输入数据进行预处理！（题目不能保证所有小木棍长度<=50）

```java
import java.util.*;
public class Test{
    public static int[] arr;
    public static int cnt = 0; //记录长度<=50的小木棍数量
    public static int sum = 0; //记录所有长度<=50的小木棍的长度之和
    public static boolean[] visited; //标记小木棍的使用状态

public static boolean dfs(int targetCount, int nowCount, int nowSum, int len, int index){
        //targetCount: 需要拼凑的木棍数量
        //nowCount: 目前已经拼凑的数量
        //nowSum: 当前由若干小木棍拼凑的长度
        //len: 此次枚举的木棍长度
        //index: 遍历的下标

if(nowCount == targetCount){ //所有小木棍恰好能拼凑出 targetCount根长度为len的木棍
            return true;
        }
        if(nowSum == len){ //已经拼凑出一根长度为len的木棍，接着往下尝试
            return dfs(targetCount, nowCount + 1, 0, len, cnt);
        }

for(int i = index; i >= 0; i--){
            if(!visited[i] && nowSum + arr[i] <= len){ //剪枝2：保证小木棍拼凑的长度 <= len
                visited[i] = true;
                if(dfs(targetCount, nowCount, nowSum + arr[i], len, i-1)){ //此处记得将dfs()的结果return
                    return true;
                }
                visited[i] = false;
                //剪枝3：如果当前arr[i]尝试失败后(因为只有失败后才回溯到此处)，证明arr[i]对当前的结果无作用，直接跳过
                while(i > 0 && arr[i] == arr[i-1]) i--;
            }

}
        return false;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        arr = new int[n+1];
        visited = new boolean[n+1];

int num;
        for(int i = 1; i <= n; i++){
            num = sc.nextInt();
            if(num <= 50){ //长度>50的小木棍全都抛弃，不然AC不了
                arr[++cnt] = num;
                sum += num;
            }
        }

//按从小到大排序，然后逆序遍历
        Arrays.sort(arr, 1, cnt + 1);

//枚举切割前木棍的长度，其范围为[最长的小木棍长度，所有小木棍长度之和]
        //注意这里说的小木棍都是指长度<=50的
        for(int len = arr[cnt]; len <= sum; len++){
            //剪枝1：sum必须能整除木棍的长度
            if(sum % len == 0){
                Arrays.fill(visited, false);

//切割前木棍的数量
                int k = sum / len;

//我们需要去利用现有的小木棍，使其能刚好拼凑出k根长度为len的木棍
                //如果当前的方案能够生效，必然是最小的长度
                if(dfs(k, 0, 0, len, cnt)){
                    System.out.println(len);
                    return;
                }
            }
        }

}
}
```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

mostshadow

TA的其他文章

你可能喜欢

时间转换（Java代码）

C二级辅导-阶乘数列（C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

信息学奥赛一本通T1442-小木棍（JAVA）

评论区

精彩推荐

C二级辅导-进制转换（C语言代码）

C二级辅导-计负均正（C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言考试练习题_保留字母（C语言代码）

简单的a+b （C语言代码）

字符串输入输出函数（C++代码）（都当成字符串吧hhhhhhhh）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

剪刀石头布（C语言代码）不知道怎么直接在scanf中用枚举变量

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

兰顿蚂蚁（C++代码）

mostshadow

TA的其他文章

你可能喜欢

时间转换 （Java代码）

C二级辅导-阶乘数列 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

信息学奥赛一本通T1442-小木棍（JAVA）

评论区

精彩推荐

C二级辅导-进制转换 （C语言代码）

C二级辅导-计负均正 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言考试练习题_保留字母 （C语言代码）

简单的a+b （C语言代码）

字符串输入输出函数 （C++代码）（都当成字符串吧hhhhhhhh）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

剪刀石头布 （C语言代码）不知道怎么直接在scanf中用枚举变量

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

兰顿蚂蚁 （C++代码）

时间转换（Java代码）

C二级辅导-阶乘数列（C语言代码）

　　评论区

C二级辅导-进制转换（C语言代码）

C二级辅导-计负均正（C语言代码）

C语言考试练习题_保留字母（C语言代码）

字符串输入输出函数（C++代码）（都当成字符串吧hhhhhhhh）

剪刀石头布（C语言代码）不知道怎么直接在scanf中用枚举变量

兰顿蚂蚁（C++代码）