题目链接

https://www.dotcpp.com/oj/problem1551.html

题目大意

一圈，n个位置，m棵树，树不能挨着，必须把m棵树全部种下。每个位置都有一个美观度，种下树就可以获得对应位置的美观度，问最大美观度。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=35;
int ans,n,m;
int a[N];//美观度
int f[N];//用于标记i位置的花坛是否种树了
void dfs(int step,int sum,int num){//花坛序号 总美观度 已种树数
        //结束判断
    if(num>m) return ;//已种树数超过m棵
    if(step==n+1){//一圈转完，要是满足以下条件刷新答案，不满足就直接return了。
        if((!f[n]||!f[1])&&num==m){
            ans=max(ans,sum);
        }
        return ;
    }

        //开始判断
    if(step==1){//处于第一个位置时，可以选在在此种树，或者不种
        dfs(step+1,sum,num);//no
        f[step]=1;
        dfs(step+1,sum+a[step],num+1);//yes
        f[step]=0;
        return ;
    }
    if(!f[step-1]){//前一个位置没种树，那么本位置可以种树，也可以不种树
        f[step]=1;
        dfs(step+1,sum+a[step],num+1);//yes
        f[step]=0;
    }
    dfs(step+1,sum,num);//no
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    if(m>n/2){cout<<"Error!"<<endl;return 0;}//特判，没法种下全部m棵树

    dfs(1,0,0);
    cout<<ans<<endl;
}

总结

开始想着用dp做，没做出来。
dfs的三个return条件让我感到诧异，牛！
还可以用优先队列做，有时间会附上链接的！