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

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

public class 种树 {

    static int n, m;
    static int[] arr, isVisted;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();// n个种树的位置
        m = sc.nextInt();// m棵树苗
        arr = new int[n + 1];
        isVisted = new int[n + 1];// 记录该点是否种树了
        for (int i = 1; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        dfs(0, 0, 0);// 深度搜索各种可能性
        if (max == Integer.MIN_VALUE) {
            System.out.println("Error!");
        } else {
            System.out.println(max);
        }
    }

    static int max = Integer.MIN_VALUE;// 最大美观度

    /**
     * 
     * @param i
     *            第几个地点
     * @param step
     *            种树的个数
     * @param val
     *            价值总和
     */
    public static void dfs(int i, int step, int val) {
        if (step > m) {// 剪枝如果种树的个数大于了需要种的个数那么就不用继续递归了
            return;
        }
        if (step == m) {// 如果目前种树的个数等于需要的个数
            max = Math.max(max, val);// 比较价值大小
            return;
        }
        for (int j = i + 1; j < arr.length; j++) {
            // j == 1 第一个点
            // j == n && isVisted[1] == 0 最后一个点 判断第一个点有没有被种过
            // isVisted[j - 1] == 0判断前一个点是否别种过
            if (j == 1 || ((j == n && isVisted[1] == 0 || j > 1 && j < n) && isVisted[j - 1] == 0)) {
                isVisted[j] = 1;// 标记这个点已经被种树了
                dfs(j, step + 1, val + arr[j]);
                isVisted[j] = 0;// 回溯
            }

        }
    }
}