📝 题目大意

给定 $N$ 个砝码，每个砝码 $i$ 的重量为 $A_i$。若一个正整数可以由不超过 $3$ 个不同的砝码的重量之和表示，则称其为"好整数"。求在 $[1, W]$ 范围内有多少个好整数。

💡 解题思路

1. 题目分析：

   • $N \le 300$，$W \le 10^6$，$A_i \le 10^6$。
   • 核心操作是从 $N$ 个元素中选 $1$、$2$ 或 $3$ 个不同的元素求和，看哪些和值 $\le W$ 可以被覆盖。
   • $N$ 最大只有 $300$，$O(N^3) \approx 2.7 \times 10^7$ 在可接受范围内，因此直接枚举所有组合是最简单且正确的做法。

2. 算法推导：

   • 使用布尔数组 visited 大小为 $W+1$，visited[x] = true 表示重量 $x$ 可以被拼出。
   • 选 1 个：遍历所有 $A_i$，若 $A_i \le W$ 则标记 visited[A_i] = true。
   • 选 2 个：双重循环枚举所有无序对 $(i, j)$（$i < j$），计算 $sum = A_i + A_j$，若 $sum \le W$ 则标记。
   • 选 3 个：三重循环枚举所有无序三元组 $(i, j, k)$（$i < j < k$），计算 $sum = A_i + A_j + A_k$，若 $sum \le W$ 则标记。
   • 最后遍历 $1 \sim W$，统计 visited[i] 为 true 的个数即为答案。

3. 边界与细节：

   • 砝码重量可能相同（如样例 3），但题目要求不同的砝码（下标不同），所以即使 $A_i$ 值相同，只要下标不同就视为不同砝码。枚举时用下标 $i < j < k$ 保证了这一点。
   • 求和时只关心 $sum \le W$，超过 $W$ 的直接忽略，无需标记（数组大小只有 $W+1$，避免越界）。
   • 注意 visited 数组大小设置为 $W+1$，下标从 $1$ 到 $W$ 有意义。

⏱️ 复杂度分析

• 时间复杂度：$O(N^3)$，其中枚举 $1$ 个、$2$ 个、$3$ 个砝码的组合分别需要 $O(N)$、$O(N^2)$、$O(N^3)$，总复杂度由 $O(N^3)$ 主导。$N=300$ 时约 $2.7 \times 10^7$ 次运算，可以通过。
• 空间复杂度：$O(W)$，即 visited 数组的大小。$W \le 10^6$，约 $1$ MB，完全可行。

💻 标准代码 (C++)

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 优化输入输出效率
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, W;
    if (!(cin >> N >> W)) return 0;

    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // visited[x] 用于标记重量 x 是否可以被拼凑出来
    // 因为只需要统计不超过 W 的好整数，所以数组大小设为 W + 1 即可
    vector<bool> visited(W + 1, false);

    // 1. 选择 1 个砝码
    for (int i = 0; i < N; ++i) {
        if (A[i] <= W) {
            visited[A[i]] = true;
        }
    }

    // 2. 选择 2 个不同的砝码（枚举所有无序对 (i, j)，i < j）
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            int sum = A[i] + A[j];
            if (sum <= W) {
                visited[sum] = true;
            }
        }
    }

    // 3. 选择 3 个不同的砝码（枚举所有无序三元组 (i, j, k)，i < j < k）
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            for (int k = j + 1; k < N; ++k) {
                int sum = A[i] + A[j] + A[k];
                if (sum <= W) {
                    visited[sum] = true;
                }
            }
        }
    }

    // 统计在 1 到 W 范围内有多少个被标记的好整数
    int ans = 0;
    for (int i = 1; i <= W; ++i) {
        if (visited[i]) {
            ans++;
        }
    }

    cout << ans << "\n";

    return 0;
}