JoshuaLi

用户名：dotcpp0615377

访问量：1340

签　名：

等　　级
排　　名	29603
经　　验	514
参赛次数	0
文章发表	3
年　　龄	0
在职情况	学生
学　　校	东莞理工学院
专　　业

　　自我简介：

TA的其他文章

模板题Dijkstra (JAVA)
浏览：60

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

回溯+剪枝（java）

　　作者: JoshuaLi　　　　发表时间：2023-05-14 21:23:51 浏览：1104　|　评论：0　

原题链接：蓝桥杯2023年第十四届省赛真题-买瓜

##回溯+剪枝

'''java

import java.util.Scanner;
	public class Main {

static int n, m, nums[], min = 100;
		static long suf[];

public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);
			n = sc.nextInt();
			m = sc.nextInt();
			nums = new int[n];
			for (int i = 0; i < n; i++) {
				nums[i] = sc.nextInt();
			}
			suf = new long[n + 1];// 后缀和，要开long不然会爆
			for (int i = n - 1; i >= 0; i--) {
				suf[i] = suf[i + 1] + (long) nums[i];
			}

dfs(0, 0, 0);
			if (min == 100)
				System.out.println(-1);
			else
				System.out.println(min);

}

static void dfs(int i, double sum, int c) {
			if (suf[i] + sum < m) return;// 剪枝，如果当前sum加上剩余所有值都小于m，即可提前结束
			if (sum > m) return; 		 // 剪枝，如果当前sum大于m，即可提前结束
			if (c >= min) return;		 // 剪枝，劈瓜的次数大于等于最小值，即使能满足要求m也没有意义，因为它不是最小的
			if (sum == m) {
				min = c;
			}

for (int j = i; j < n; j++) {
				sum += nums[j]; 		//整个西瓜拿走
				dfs(j + 1, sum, c);
				sum -= nums[j] / 2.0;	//拿走一半
				dfs(j + 1, sum, c + 1);
				sum -= nums[j] / 2.0;	//不拿走
			}

}

}
'''

0.0分

9 人评分

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

JoshuaLi

TA的其他文章

你可能喜欢

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

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

The 3n + 1 problem （C语言代码）

汽水瓶（C语言代码）怎么答案错误？？？？？

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

回溯+剪枝（java）

评论区

精彩推荐

化学品问题（C语言代码）

C二级辅导-等差数列（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

母牛的故事（C语言代码）

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

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

C语言训练-列出最简真分数序列* （C语言代码）

WU-C语言程序设计教程（第三版）课后习题12.1 （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

1124题解

JoshuaLi

TA的其他文章

你可能喜欢

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

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

The 3n + 1 problem （C语言代码）

汽水瓶 （C语言代码）怎么答案错误？？？？？

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

回溯+剪枝（java）

评论区

精彩推荐

化学品问题 （C语言代码）

C二级辅导-等差数列 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

母牛的故事 （C语言代码）

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

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

C语言训练-列出最简真分数序列* （C语言代码）

WU-C语言程序设计教程（第三版）课后习题12.1 （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

1124题解

汽水瓶（C语言代码）怎么答案错误？？？？？

　　评论区

化学品问题（C语言代码）

C二级辅导-等差数列（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

母牛的故事（C语言代码）