1 条题解
-
0
【本题解由站长编写】
两个包装规格 a、b 由输入给出(不是硬编码的 4 和 7),求最大的、无法用若干个 a 包和若干个 b 包凑出的整数。当 gcd(a,b)=1 时经典结论是最大不能表示的数为
a*b - a - b(Frobenius 数);三组数据(10 13→107、30 41→1159、257 191→48639)都与该公式精确吻合。不放心时也可以用 DP 兜底:dp[0]=true,dp[i] = (i>=a && dp[i-a]) || (i>=b && dp[i-b]),在 0..a*b 范围内找最后一个dp[i]==false的 i。代码(C++17)
#include <bits/stdc++.h> using namespace std; int main() { int a, b; cin >> a >> b; // 两个规格互质时,最大不能凑出的数就是 a*b-a-b cout << a * b - a - b << endl; return 0; }
- 1
信息
- ID
- 4096
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者