蓝桥杯算法提高VIP-种树-题解（Java代码）

解题思路:

注意事项:dfs

参考代码:

import java.util.Scanner;

//DFS

public class llq1{

static final int maxn=35;

static int N=0;

static int M=0;

static int val[]=new int[maxn];

static boolean isPlanted[]=new boolean [maxn];//是否已经种了树

static int ans=0;

static int tmp=0;

public static void main(String[] args) {

Scanner s=new Scanner(System.in);

N=s.nextInt();

M=s.nextInt();

for(int i=1;i<N+1;i++) {

val[i]=s.nextInt();

}

if(M>N/2) {

System.out.println("Error!");

return;

}

dfs(1,0);

System.out.println(ans);

}

private static void dfs(int pos, int cnt) {//pos位置，cnt已经种了多少树

// TODO Auto-generated method stub

if(cnt==M) {

ans=Math.max(ans, tmp);

return;

}

for(int i=pos;i<=N;i++) {

if(check(i)) {

tmp+=val[i];

isPlanted[i]=true;

dfs(i,cnt+1);

isPlanted[i]=false;

tmp-=val[i];

}

}

}

private static boolean check(int pos) {//检查是否可以种树

// TODO Auto-generated method stub

if(pos>N||isPlanted[pos]||isPlanted[(pos+1)%N]||isPlanted[(pos-1)%N])

return false;

return true;

}

}