分治dfs

import java.util.*;

public class Main {

    static int max;
    static int n;
    static int a[];
    static int b[];
    public static void main(String[] args) {

        Scanner jin = new Scanner(System.in);
        n = jin.nextInt();
        a = new int[n+1];
        b = new int[n];
        for(int i=1;i<=n;i++) a[i] = jin.nextInt();
        for(int i=1;i<n;i++) b[i] = jin.nextInt();
        f(0, 0, 1);
        System.out.println(max);

    }

    public static void f(int num, int cs, int bs){
        if(num < 0){
            System.out.println(-1);
            System.exit(0);
        }
        if(bs == n){
            if(cs < 3)
                max = Math.max(max, num+a[n]);
            else
                max = Math.max(max, num);
            return;
        }

        if(num >= b[bs])  f(num-b[bs], cs, bs+1);
        if(cs < 3)  f(num+a[bs]-b[bs], cs+1, bs+1);

    }

}

这里用的分治法，开始理解错了题目，漏了一个小明只能选择三个补给点。

开始没有想到这个方法的参数是啥，1.num糖果的总数，2.cs也就是补给数（补给数不超过三个），3.下标。开始是没有糖果的，也没有拿到补给，下标从1开始。所以dfs（0,0,1），在dfs中，出口是num<0，当下标bs等于n的时候，那么就可以开始判断，如果补给数没有到3，那么可以直接拿最后一个补给，再同max比较，如果补给数到了3，那么就不能加上最后一个补给，直接和max比较。

接下来是分治法，两个判断条件，如果糖果数大于所需要的的糖果，那么就可以继续dfs，另一个就是如果补给站小于3，那么可以添加一个补给继续dfs。