1 条题解
-
0
【本题解由站长编写】
先看全部体积的最大公约数:大于 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
- 上传者