P8742 [蓝桥杯 2021 省 AB] 砝码称重-Java版

[蓝桥杯 2021 省 AB] 砝码称重

题目描述

你有一架天平和 $N$ 个砝码, 这 $N$ 个砝码重量依次是 $W_1,W_2,\cdots ,W_N$ 。 请你计算一共可以称出多少种不同的重量?

注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 $N$ 。

第二行包含 $N$ 个整数: $W_1,W_2,W_3,\cdots ,W_N$ 。

输出格式

输出一个整数代表答案。

样例 #1

样例输入 #1

3
1 4 6

样例输出 #1

10

提示

【样例说明】

能称出的 10 种重量是: $1、2、3、4、5、6、7、9、10、11$ 。

$$\begin{array}{rl}& 1=1\\ & 2=6-4(\text{ 天平一边放 }6,\text{ 另一边放 4) }\\ & 3=4-1\\ & 4=4\\ & 5=6-1\\ & 6=6\\ & 7=1+6\\ & 9=4+6-1\\ & 10=4+6\\ & 11=1+4+6\end{array}$$

【评测用例规模与约定】

对于 $50\%$ 的评测用例, $1\le N\le 15$ 。

对于所有评测用例, $1\le N\le 100,N$ 个砝码总重不超过 $10^5$。

蓝桥杯 2021 第一轮省赛 A 组 F 题（B 组 G 题）。

import java.util.Scanner;

public class Main {
    private static final int N = 150000;//假设砝码总重量<150000
    private static int n, sum, w;
    private static boolean[][] f = new boolean[2][2 * N + 1];//[天平][砝码重量]

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
//f[i][j] 表示在使用前 i 个砝码的情况下，能否称出重量为 j 的物品。
        f[0][N] = true;//表示不使用任何砝码时，可以称出 0 克的重量
        for (int i = 1; i <= n; ++i) {//遍历砝码
            w = scanner.nextInt();
            sum += w;
            for (int j = -sum; j <= sum; ++j) {//遍历砝码重量区间
            //i % 2 是为了在每次迭代过程中交替使用两个子数组，实现所谓的“滚动数组优化”，减少内存消耗
            //在当前考虑到了前 i 个砝码的情况下，能否组合出重量为 j 的物体
                f[i % 2][j + N] = f[(i - 1) % 2][j - w + N] || f[(i - 1) % 2][j + w + N] || f[(i - 1) % 2][j + N];
            }
        }

        int ans = 0;
        for (int i = 1; i <= sum; ++i) {
            if (f[n % 2][i + N]) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}```