题解 | #称砝码# DP

import java.util.Scanner;
import java.util.*;

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

        // 输入砝码种类数
        int n = scanner.nextInt();
        // 输入每种砝码的重量
        int[] weights = new int[n];
        for (int i = 0; i < n; i++) {
            weights[i] = scanner.nextInt();
        }
        // 输入每种砝码的数量
        int[] counts = new int[n];
        for (int i = 0; i < n; i++) {
            counts[i] = scanner.nextInt();
        }

        // 调用函数计算能称出的不同重量数
        int result = calculateDistinctWeights(n, weights, counts);
        System.out.println(result);
    }

    public static int calculateDistinctWeights(int n, int[] weights, int[] counts) {
        // 计算最大可能的重量（即每种砝码都用最大数量的和）
        int maxWeight = 0;
        for (int i = 0; i < n; i++) {
            maxWeight += weights[i] * counts[i];
        }

        // dp数组，dp[i]表示重量i是否可以称出
        boolean[] dp = new boolean[maxWeight + 1];
        dp[0] = true; // 初始条件：可以称出重量0

        // 动态规划更新dp数组
        for (int i = 0; i < n; i++) {
            int weight = weights[i];
            int count = counts[i];
            // 从后往前遍历，避免重复使用同一种砝码
            for (int j = maxWeight; j >= 0; j--) {
                // 逐个添加不同数量的该砝码
                if (dp[j]) {
                    for (int k = 1; k <= count; k++) {
                        if (j + k * weight <= maxWeight) {
                            dp[j + k * weight] = true;
                        } else {
                            break;
                        }
                    }
                }
            }
        }

        // 统计能称出的不同重量数
        int distinctWeightCount = 0;
        for (boolean canWeigh : dp) {
            if (canWeigh) {
                distinctWeightCount++;
            }
        }

        return distinctWeightCount;
    }
}