种树---dfs遍历详细说明

解题思路:
简单暴力
注意事项:
位置的合理性判断

代码只是参考  有优化空间

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 30+5;
int n,m,mx = 0;
int sum = 0;
int a[N],vs[N];//vs[i]=1表示第i处种植树 

bool check(int x,int y){//x是现在种树的位置， y是下一棵树的位置
//检验y是否合理 
    if(abs(x-y)<=1||(x==1&&vs[n]==1)||(x==n&&vs[1]==1)
    ||(y==1&&vs[n]==1)||(y==n&&vs[1]==1)){
//x,y不能相邻  x,y为首(尾)时判断 尾(首) 是否种树，有种就不允许 
        return false;
    }
    return true;//合理 
}

void dfs(int x,int v){//x表示上一棵树的位置v表示种了几个树 
    if(v==m){//已经种满了m个树 
        mx = max(mx,sum);//记录最大值 并返回 
        return;
    }
    for(int i = x;i<=n;i++){//继续遍历后面位置 看那些位置可以种树 
        if(check(x,i)&&!vs[i]){//i位置合理且没有种树 
            sum += a[i];//加上美观度 
            vs[i] = 1;//种树标记 
            dfs(i,v+1);//深入遍历 
            vs[i] = 0;//标记恢复 
            sum -= a[i];//美观度恢复 
        }
    }
}

void solve(){
    cin>>n>>m;
    
    
    for(int i = 1;i<=n;i++){
        cin>>a[i];
    }
    
    for(int i = 1;i<=n;i++){//以每一个位置为起点 去循环遍历
        sum = a[i];//首先加上起点美观度 
        memset(vs,0,sizeof(vs));//初始化种树标记 
        vs[i]=1;//起点种树 
        dfs(i,1);//继续遍历    
    }
    if(mx==0) cout<<"Error!";
    else cout<<mx;

}

int main(){ 
    solve();
    return 0;
}