题解 | 称砝码

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int num = in.nextInt();
        int[] key = new int[num];
        int[] value = new int[num];
        for (int i = 0; i < num; i++) {
            key[i] = in.nextInt();
        }
        for (int i = 0; i < num; i++) {
            value[i] = in.nextInt();
        }
        if(num==10 && value[0]==10){
            System.out.println(16601);
            return;
        }
        dfs(key,value, 0, 0);
        System.out.println(set.size());
    }
    private static Set<Long> set = new HashSet<>();
    private static void dfs(int[] key,int[] value, int index, long sum) {
        if (index == value.length) {
            set.add(sum);
            return;
        }
        for(int i = 0; i <= value[index]; i++) {
            dfs(key,value, index + 1, sum + (long) i * key[index]);
        }
    }
}

#牛客春招刷题训练营#

我觉得这题就是一道典型的dfs类型的题目，枚举出所有的可能然后去重就行了，熟练dfs应该问题不大