蓝桥杯算法提高VIP-种树-题解（C++代码）-dfs实现

参考代码:

#include<bits/stdc++.h>
using namespace std;
int a[1001]; //记录价值
int site[1001]; //记录位置是否栽树，1/0
int n, m,maxs; //maxs最大价值
bool cont(int d) //判断当前位置能否栽树（判断前一个位置当前位置和后一个位置是否栽树）。
{
	return (site[d] == 0 && site[(d - 1 + n) % n] == 0 && site[(d + 1) % n] == 0);
}
void dfs(int x,int s,int sum)
{
	site[x] = 1;
	sum += a[x];
	if (s)
	{
		for (int i =x+2; i < n; i++) //从当前位置往后递归栽树
			if (cont(i))
			{
				dfs(i, s - 1,sum);
			} 
	}
	else
	{
		if (sum > maxs) maxs = sum;
	}
	site[x] = 0;
}
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> a[i];
	if ((n/2)>=m)
	{
		for (int i = 0; i < n; i++)
		{
			dfs(i, m-1,0);
		}
	 cout << maxs<<endl;
	}
	else cout << "Error!";	
}