怎么会忘了呢

用户名：knight9

访问量：704

签　名：

等　　级
排　　名	48221
经　　验	300
参赛次数	0
文章发表	1
年　　龄	0
在职情况	学生
学　　校	沈阳工业大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-种树-题解(C++代码)（回溯法）
浏览：424

你可能喜欢

蓝桥杯算法提高VIP-种树-题解(C++代码)（回溯法）

　　作者: 怎么会忘了呢　　　　发表时间：2020-02-08 12:01:51 浏览：424　|　评论：0　

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

#概述
  刚自学数据结构与算法没两天，看了回溯法的两道经典问题———n皇后和旅行售货家问题，看到这道种树问题的时候，觉得此类需要遍历所有情况求得最优解的问题都可以用一个模板来解决。代码借鉴于网上看的别人的N皇后问题的代码，可以说几乎一样。
#思路
  通过回溯，改变数组M[i]的值遍历所有可能的种树情况，并将其中最大美观度记录下来。
#代码
```cpp
#include<iostream>
using namespace std;
int A[32] = { 0 };                          //美观度数组
int M[32] = { 0 };               //数组M[i]表示第i棵树种的位置
int Maxapprance = -1000,flag=0; //设置最大美观度的初始值
int n,m;  //种树的位置编号和树的数量
bool judge(int t) {              //判断第t棵树能否种植该位置
	if (t == 1 && M[1] > (n + 1) - (m * 2 - 1)) {
		return false;
	}
	if (t > 1) {
        if (M[t] - M[t - 1] <= 1 || M[t] - M[1] == n - 1) {
		    return false;
	    }
    }
	return true;
}
void planet(int k) {
	int x = 1;       //第一棵树
	if (k >= n / 2 + 1) {
		cout << "Error!" << endl;
		return;
	}
	while (x > 0) {
		M[x]++;
		while (M[x] <= n && !judge(x)) {
			M[x]++;
		}
		flag += A[M[x]];
		if (M[x] <= n) {
			if (x == k) {
				if (flag > Maxapprance || Maxapprance == -1000) {
					Maxapprance = flag;
				}
				flag -= A[M[x]];
			}
			else if (x < k) {
				x++;
				M[x] = 2 * (x - 1);       //每次换行设置树的初始位置
			}
		}
		else {
			x--;                       
			if (x == 1)
				flag = 0;
			else
				flag -= A[M[x]];        //回溯
		}
	}
	cout << Maxapprance << endl;
}
int main() {
	cin >> n;
	cin >> m;
	for (int i = 1;i <= n;i++) {
		cin >> A[i];
	}
	planet(m);
	return 0;
}
```

0.0分

0 人评分

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

　　评论区

精彩推荐

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

C语言训练-尼科彻斯定理（C语言代码）。。。内含证明定理

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

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

矩形面积交（C语言代码）

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

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

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

哥德巴赫曾猜测（C语言代码）

数组输出（C语言代码）

怎么会忘了呢

TA的其他文章

你可能喜欢

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

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

C语言训练-计算一个整数N的阶乘（C语言代码）

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

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

蓝桥杯算法提高VIP-种树-题解(C++代码)（回溯法）

评论区

精彩推荐

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

C语言训练-尼科彻斯定理（C语言代码）。。。内含证明定理

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

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

矩形面积交（C语言代码）

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

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

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

哥德巴赫曾猜测（C语言代码）

数组输出（C语言代码）

怎么会忘了呢

TA的其他文章

你可能喜欢

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

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

C语言训练-计算一个整数N的阶乘 （C语言代码）

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

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

蓝桥杯算法提高VIP-种树-题解(C++代码)（回溯法）

评论区

精彩推荐

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

C语言训练-尼科彻斯定理 （C语言代码）。。。内含证明定理

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

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

矩形面积交 （C语言代码）

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

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

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

哥德巴赫曾猜测 （C语言代码）

数组输出 （C语言代码）

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

C语言训练-计算一个整数N的阶乘（C语言代码）

　　评论区

C语言训练-尼科彻斯定理（C语言代码）。。。内含证明定理

矩形面积交（C语言代码）

哥德巴赫曾猜测（C语言代码）

数组输出（C语言代码）