拼多多 种树

dfs+剪枝
注意剪枝条件:
如果还剩下2k+1个坑位, 最多有k+1个树属于同一个种类
如果还剩下2k个坑位, 最多有k个树属于同一个种类

所以剪枝条件为: 2*树i的数量 > (剩余坑位+1)

package t2;

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        f();
    }

    //  存放答案的全局序列
    public static ArrayList<Integer> street = new ArrayList<>();


    public static void f() {
        Scanner sc = new Scanner(System.in);
        int n_cate = sc.nextInt();
        int[] num_tree = new int[n_cate];

        int sum = 0;

        for (int i = 0; i < n_cate; i++) {
            num_tree[i] = sc.nextInt();
            sum += num_tree[i];
        }

        boolean res = dfs(num_tree,0, sum);

        if(res==true){
            for (Integer integ :street){
                System.out.print(integ+1);
                System.out.print(" ");
            }
            System.out.println();
        }else{
            System.out.println("-");
        }


    }

    // num_tree: 每种树的数量
    // next_loc: 下一个要种树的位置
    // len_street: 道路的长度
    public static boolean dfs(int[] num_tree, int next_loc, int len_street) {
        // 树种满了
        if(next_loc==len_street)
            return true;

        // 剪枝
        for (int i1 : num_tree) {
            if(2*i1>(len_street-next_loc+1)) return false;
        }

        // dfs
        for (int i = 0; i < num_tree.length; i++) {
            if (next_loc == 0 || (i != street.get(next_loc-1) && num_tree[i] > 0)) {
                street.add(i);
                num_tree[i]--;
                boolean res = dfs(num_tree, next_loc+1, len_street);
                if(res==true) return true;
                num_tree[i]++;
                street.remove(street.size()-1);
            }
        }


        return false;
    }


}