【题目来源】
洛谷：[P2737 USACO4.1] 麦香牛块 Beef McNuggets - 洛谷
【题目描述】
农夫布朗的奶牛们正在进行斗争，因为它们听说麦当劳正在考虑引进一种新产品：麦香牛块。奶牛们正在想尽一切办法让这种可怕的设想泡汤。奶牛们进行斗争的策略之一是“劣质的包装”。“看，”奶牛们说，“如果你只用一次能装 \(3\) 块、\(6\) 块或者 \(10\) 块的三种包装盒包装麦香牛块，你就不可能满足一次只想买 \(1\)、\(2\)、\(4\)、\(5\)、\(7\)、\(8\)、\(11\)、\(14\) 或者 \(17\) 块麦香牛块的顾客了。劣质的包装意味着劣质的产品。”
你的任务是帮助这些奶牛。给出包装盒的种类数 \(N\ (1 \le N \le 10)\) 和 \(N\) 个代表不同种类包装盒容纳麦香牛块个数的正整数 \(b_i\ (1 \le b_i \le 256)\)，输出顾客不能用上述包装盒（每种盒子数量无限）买到麦香牛块的最大块数。如果所有购买方案都能得到满足或者不存在不能买到块数的上限，则输出 \(0\)。不能买到的最大块数（如果它存在）不超过 \(2\times 10^9\)。
【输入】
第 \(1\) 行：包装盒的种类数 \(N\)。
第 \(2\) 行到 \(N+1\) 行：每个种类包装盒容纳麦香牛块的个数。
【输出】
输出文件只有一行数字：顾客不能用包装盒买到麦香牛块的最大块数或 \(0\)（如果所有购买方案都能得到满足或者顾客不能买到的块数没有上限）。
【输入样例】
3
3
6
10
【输出样例】
17
【算法标签】
《洛谷 P2737 麦香牛块》 #数学# #USACO#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 15; // 最大硬币数量
const int MAX_VAL = 65025; // 最大可能金额（256 * 256 - 256 - 256）int n; // 硬币数量
int a[N]; // 存储硬币面值
int dp[MAX_VAL + 5]; // 动态规划数组，dp[j]表示能否凑出金额j
int ans; // 存储最大无法凑出的金额int main()
{// 输入硬币数量cin >> n;// 输入每个硬币的面值for (int i = 1; i <= n; i++){cin >> a[i];}// 初始化动态规划数组dp[0] = 1; // 金额0总是可以凑出（不选任何硬币）// 完全背包：计算所有可凑出的金额for (int i = 1; i <= n; i++){// 遍历所有可能的金额for (int j = a[i]; j <= MAX_VAL; j++){// 如果j-a[i]可以凑出，那么j也可以凑出dp[j] |= dp[j - a[i]];}}// 从大到小查找第一个无法凑出的金额ans = 0; // 初始化为0（表示所有金额都能凑出）for (int i = MAX_VAL; i >= 1; i--){// 如果当前金额无法凑出if (dp[i] == 0){ans = i; // 记录最大无法凑出的金额break; // 找到后立即退出循环}}// 如果所有金额都能凑出（ans >= MAX_VAL 表示没找到无法凑出的金额）if (ans == MAX_VAL){ans = 0; // 设置结果为0}// 输出最大无法凑出的金额cout << ans << endl;return 0;
}
【运行结果】
3
3
6
10
17