梁康承

用户名：uq_48132650349

访问量：2216

签　名：

等　　级
排　　名	1714
经　　验	2693
参赛次数	4
文章发表	6
年　　龄	0
在职情况	学生
学　　校	湖北生物科技职业学院
专　　业	计算机应用

　　自我简介：

TA的其他文章

蓝桥杯算法训练VIP-装箱问题-题解（Java代码）
浏览：402

蓝桥杯算法提高VIP-种树-题解（Java代码）- 回溯 · 改
浏览：324

蓝桥杯2014年第五届真题-重复模式-题解（Java代码）正则解法
浏览：373

你可能喜欢

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

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

蓝桥杯算法提高VIP-种树-题解（Java代码）- 回溯 · 改

　　作者: 梁康承　　　　发表时间：2020-10-13 11:01:16 浏览：324　|　评论：0　

原题链接：蓝桥杯算法提高VIP-种树

import java.util.Scanner;

public class Main {
		public static void main(String[] args) {
			Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt(), m = scanner.nextInt();
			int[] dp = new int[n];
			boolean[] isMatch = new boolean[n];
			for (int i = 0; i < n; i++) {
				dp[i] = scanner.nextInt();
			}
			if (m * 2 > n) {
				// 此处为当种完 m课树时必然有邻位
				System.out.println("Error!");
			} else {
				/**
				 * m : 提供的树种个数
				 * cur : 循环下标，当前是第 i个树坑，为下一次循环做的起点
				 * dp : 树坑的美观度数组
				 * isMatch : 记录哪个树坑被种下
				 */
				Fn(m, 0, dp, isMatch);
				System.out.println(sum);
			}
		}

// 可能题目给出的树坑美观度全部为负数
		static int sum = Integer.MIN_VALUE;

static void Fn(int m, int cur, int[] dp, boolean[] isMatch) {
			// 为0时即全部种下
			if (m == 0) {
				int dnf = 0;
				for (int i = 0; i < isMatch.length; i++) {
					if (isMatch[i]) {
						dnf += dp[i];
					}
				}
				// 求出美观度最大值
				sum = Math.max(sum, dnf);
				return;
			}
			for (int i = cur; i < isMatch.length; i++) {
				if (i == 0 || Bn(i, isMatch)) {
					// 标记为 true即为种下
					isMatch[i] = true;
					// 下标 +1，可以去重复，节省时间
					Fn(m - 1, i + 1, dp, isMatch);
					// 此处为回溯，将树坑回复为false，可重复利用
					isMatch[i] = false;
				}
			}
		}

static boolean Bn(int n, boolean[] isMatch) {
			if (isMatch[n - 1]) {
				// 判断上一个树坑是否被使用
				return false;
			}
			if (n == isMatch.length - 1 && isMatch[0]) {
				// 当 n == isMatch.length - 1时，即为种在最后一个树坑，此处还要判断0号树坑是否被使用
				return false;
			}
			return true;
		}
	}

0.0分

1 人评分

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

梁康承

TA的其他文章

你可能喜欢

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

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

字符逆序（C语言代码）

字符串的输入输出处理（C语言代码）

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

蓝桥杯算法提高VIP-种树-题解（Java代码）- 回溯 · 改

评论区

精彩推荐

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

P1001 （C语言代码）

大神老白（C语言代码）

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

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

1011题解

1013题解

循环入门练习5 （C语言代码）

DNA （C语言代码）

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

梁康承

TA的其他文章

你可能喜欢

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

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

字符逆序 （C语言代码）

字符串的输入输出处理 （C语言代码）

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

蓝桥杯算法提高VIP-种树-题解（Java代码）- 回溯 · 改

评论区

精彩推荐

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

P1001 （C语言代码）

大神老白 （C语言代码）

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

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

1011题解

1013题解

循环入门练习5 （C语言代码）

DNA （C语言代码）

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

字符逆序（C语言代码）

字符串的输入输出处理（C语言代码）

　　评论区

大神老白（C语言代码）