跳至正文

1 条题解

  • 0
    @ 2026-10-7 20:54:52

    【本题解由站长编写】

    先看全部体积的最大公约数:大于 1 时只能装出它的倍数,不能装出的体积有无限多个,输出 0;含有体积 1 时任何正体积都能装出,同样输出 0。否则做完全背包可达性 DP:最小体积不超过 500、最大公约数为 1 时,从某个不大的界(如 500×500+1)开始往上全部可达,从高到低扫描第一个不可达的体积就是答案。

    代码(C++17)

    #include <bits/stdc++.h>
    using namespace std;
    int main() {
        int n;
        cin >> n;
        vector<int> items(n);
        for (int i = 0; i < n; i++) cin >> items[i];
        int g = 0;
        for (int v : items) g = __gcd(g, v);
        bool hasOne = false;
        for (int v : items) if (v == 1) hasOne = true;
        if (g > 1 || hasOne) {
            cout << 0 << '\n';
            return 0;
        }
        const int BOUND = 500 * 500 + 1;
        vector<char> reach(BOUND + 1, 0);
        reach[0] = 1;
        for (int v : items)
            for (int x = v; x <= BOUND; x++)
                if (reach[x - v]) reach[x] = 1;
        int answer = 0;
        for (int x = BOUND; x >= 1; x--)
            if (!reach[x]) { answer = x; break; }
        cout << answer << '\n';
        return 0;
    }
    
    • 1

    信息

    ID
    4291
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    0
    已通过
    0
    上传者