题解 | #称砝码#DP

import java.math.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.stream.*;
import java.util.regex.*;
import java.util.function.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int[] m = new int[n];
        for (int i = 0; i < n; i++) {
            m[i] = in.nextInt();
        }

        int total = 0;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int count = in.nextInt();
            for (int j = 0; j < count; j++) {
                list.add(m[i]);
            }
        }

        // timeout
        // Set<Integer> ways = new HashSet<>();
        // move(list, 0, new ArrayList<>(), ways);
        // System.out.println(ways.size());

        // DP
        Set<Integer>[] d = new Set[list.size() + 1];
        d[0] = new HashSet<>(Arrays.asList(new Integer[] {0}));
        for (int i = 1; i < list.size() + 1 ; i++) {
            Integer curr = list.get(i - 1);

            // 使用砝码
            Set<Integer> newSet = d[i - 1].stream()
                                  .mapToInt(a-> a + curr).boxed()
                                  .collect(Collectors.toCollection(HashSet::new));
            // 不使用砝码
            newSet.addAll(d[i - 1]);

            d[i] = newSet;
        }
        System.out.println(d[list.size()].size());
    }

    // 超时
    static void move(List<Integer> list, int step, List<Integer> way,
                     Set<Integer> ways) {
        if (step == list.size()) {
            ways.add(way.stream().mapToInt(Integer::intValue).sum());
            return;
        }

        // 2 ways
        move(list, step + 1, new ArrayList<>(way), ways);
        List<Integer> newWay = new ArrayList<>(way);
        newWay.add(list.get(step));
        move(list, step + 1, newWay, ways);
    }
}