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

477 阅读 4 评论 0 点赞

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 人评分

本文分类：题解列表
浏览次数：477 次浏览
发布日期：2020-03-09 10:57:50
本文链接：https://blog.dotcpp.com/a/67676

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

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

评论列表共有 4 条评论

发表评论取消回复

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

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 4 条评论

发表评论 取消回复

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

评论列表共有 4 条评论

发表评论取消回复