梁康承

用户名：Heta

访问量：2114

签　名：

从入门到入土

等　　级
排　　名	1520
经　　验	2717
参赛次数	5
文章发表	4
年　　龄	20
在职情况	学生
学　　校	湖北生物科技职业学院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-种树（Java代码）—回溯
浏览：284

蓝桥杯算法提高VIP-连接乘积-题解(Java代码)-正则解法
浏览：191

蓝桥杯算法提高VIP-项链-题解(Java代码)-正则
浏览：302

你可能喜欢

A+B for Input-Output Practice (III) （C语言代码）

蓝桥杯算法提高VIP-种树（Java代码）—回溯

　　作者: 梁康承　　　　发表时间：2020-03-09 10:57:50 浏览：284　|　评论：1　

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

import java.util.Scanner;
	import java.util.Stack;

// 树类
	class num {
		public int ID;  // 编号
		public int sum;  // 美观度
	}

public class Main {
		public static void main(String[] args) {
			Scanner scanner = new Scanner(System.in);
			// m为树类集合总长度，n为需求量
			int m = scanner.nextInt(), n = scanner.nextInt();
			num[] item = new num[m];
			for (int i = 0; i < item.length; i++) {
				item[i] = new num();
				item[i].ID = i + 1;
				item[i].sum = scanner.nextInt();
			}

// 当n * 2 > m时，必然会有相邻的树种
			if (n * 2 > m) System.out.println("Error!");
			else {
				Cn(item, n, 0, 0);
				System.out.println(count);
			}
		}

// 总美观度，考录到美观度可能为负数，所以将总美观度的初始值设为int的最小值
		static int count = Integer.MIN_VALUE;
		// 使用堆栈储存树类
		static Stack<num> all = new Stack<num>();

/**
		 * @param shu   元素集合
		 * @param targ  要选多少个元素
		 * @param has   当前有多少个元素
		 * @param cur   当前选到的下标
		 */
		static void Cn(num[] shu, int targ, int has, int cur) {
			// 当栈长度达到所需求的数量n时，遍历出元素中所有的美观度
			if(has == targ) {
				int net = 0;
					for (num item : all) {
						net += item.sum;
					}
				// 比较每次得到的总美观度，求出最大值
				count = Math.max(count, net);
				return;
			}

for(int i = cur; i < shu.length; i++) {
				/**
				 * 此处做两个判断
				 * 一、判断是否有重复元素
				 * 二、判断是否有邻位元素
				 */
				if(!all.contains(shu[i]) && Jn(shu[i], shu.length)) {
					all.add(shu[i]);
					Cn(shu, targ, has + 1, i);
					all.pop();  // 此处为回溯重点，将旧元素移除，添加新元素，就形成新集合
				}
			}
		}

static boolean Jn(num text, int targ) {
			/**
			 * 一、先遍历出当前栈中有哪些元素
			 * 二、比较编号，有没有邻位
			 *
			 * text为比较元素，targ为树类集合长度m
			 */
			for (num item : all) {
				if (item.ID == (text.ID + targ - 1) % targ || item.ID == (text.ID + 1) % targ) return false;
			}
			return true;
		}
	}

0.0分

1 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

Plaire7

头看大了 唉

2020-09-01 17:04:54

梁康承

TA的其他文章

你可能喜欢

C二级辅导-统计字符（C++代码）

单词个数统计（Java代码）

A+B for Input-Output Practice (III) （C语言代码）

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

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

蓝桥杯算法提高VIP-种树（Java代码）—回溯

评论区

精彩推荐

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

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

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

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

钟神赛车（C++代码）

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

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

1017题解

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

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

梁康承

TA的其他文章

你可能喜欢

C二级辅导-统计字符 （C++代码）

单词个数统计 （Java代码）

A+B for Input-Output Practice (III) （C语言代码）

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

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

蓝桥杯算法提高VIP-种树 （Java代码）—回溯

评论区

精彩推荐

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

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

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

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

钟神赛车 （C++代码）

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

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

1017题解

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

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

C二级辅导-统计字符（C++代码）

单词个数统计（Java代码）

蓝桥杯算法提高VIP-种树（Java代码）—回溯

　　评论区

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

钟神赛车（C++代码）