蓝桥杯算法提高VIP-种树

题目

题目链接

题解

DFS。

挺基础的。

对于每个位置两种选择，种或者不种；种的条件是与之相邻的位置没种树；

当搜索到最后一个位置时，特判一下，如果这个位置的前后位置均没有种树，且种下这棵树就是第m棵，那么就可以选这个位置种，同时更新最大值。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 50;

int n, m, sum, a[N], vis[N], ans = -0x3f3f3f3f;

void dfs(int x, int value) {
	if(sum == m) {ans = max(ans, value); return ;} // 种了m棵树了，更新最大值，返回 
	if(x == n) { // 当遇到最后一个位置的时候，特判一下 
		if(!vis[1] && !vis[x-1] && sum+1 == m) // 如果这个位置相邻的两侧均没种树，并且在这里种树后数量刚好为m，则种树 
			ans = max(ans, value+a[x]); 
		return ; 
	}
	
	if(!vis[x-1]) { // 若x前面的位置没有被种树 
		sum ++; // 已种树的数量++ 
		vis[x] = 1; // 在x处种树，标记一下 
		dfs(x+1, value+a[x]); // value+a[x]为当前美观程度 
		vis[x] = 0; // 回溯，下同 
		sum --;
	}
	
	dfs(x+1, value); // 不种，直接搜索下一个位置 
}

int main() {
	cin>>n>>m;
	for(int i = 1;i <= n;i ++) cin>>a[i];
	
	dfs(1, 0);
	
	if(ans == -0x3f3f3f3f) puts("Error!");
	else cout << ans << endl;
}