Usaco 4.1 麦香牛块 （Beef McNuggets）Solution
Beef McNuggets麦香牛块
Hubert Chen
译 by ragazza gatti
描述
农夫布朗的奶牛们正在进行斗争，因为它们听说麦当劳正在考虑引进一种新产品：麦香牛块。奶牛们正在想尽一切办法让这种可怕的设想泡汤。奶牛们进行斗争的策略之一是“劣质的包装”。“看，”，奶牛们说，“如果你只用一次能装3块、6块或者10块的三种包装盒包装麦香牛块，你就不可能满足一次只想买1、2、4、5、7、8、11、14或者17块麦香牛块的顾客了。劣质的包装意味着劣质的产品。”
你的任务是帮助这些奶牛。给出包装盒的种类数N(1<=N<=10)和N个代表不同种类包装盒容纳麦香牛块个数的正整数(1<=i<=256)，输出顾客不能用上述包装盒(每种盒子数量无限)买到麦香牛块的最大块数。如果在限定范围内所有购买方案都能得到满足或者顾客不能买到的块数没有上限，则输出0。范围限制是所有不超过2,000,000,000的正整数。
格式
PROGRAM NAME: nuggets
INPUT FORMAT:
(file nuggets.in)
第1行: 包装盒的种类数N
第2行到N+1行: 每个种类包装盒容纳麦香牛块的个数
OUTPUT FORMAT:
(file nuggets.out)
输出文件只有一行数字：顾客不能用包装盒买到麦香牛块的最大块数或0(如果在限定范围内所有购买方案都能得到满足或者顾客不能买到的块数没有上限)。
SAMPLE INPUT
3
3
6
10
SAMPLE OUTPUT
17
不难看出，题目抽象化为：
给定自然数列(a1, a2, ..., an)
和集合{bi | bi∈N＋}
求最大的不能用 ∑ai*bi 表示的自然数。
首先，根据题目的规模。上限较大，达到maxlongint，提示我们可能用数学方法。最大单包容量256和种类数10提示我们用动态规划；上限和单包容量的巨大差距又似乎提示我们运用离散化∼
于是分析每种算法。
首先离散化不可能，因为题目本身的直观的解就是高度离散的，也很难估计不同数值的个数。加上本题并非典型的基于二分结构或矩阵结构的题目，似乎离散化没有什么帮助。
考虑动态规划。朴素的装箱，用f[i,j]表示用1－i个物体填充容量为j的箱子是否可以装完。显然：
f[i,j]=f[i-1,j]or f[i,j-a[i]]
看上限，我们可以知道，
若令min＝min{ai}，
只需找到连续的ai min个可以填充的元素。但是这仍然得不到适当的界。甚至不知道dp的数组要多大。如果最大容量比较大，绝对没办法刷数组。
考虑数学方法。显而易见，针对只有两种物体时，如果二物体的容职的非互质，显然没有上限，否则上限为:
a1a2-a1-a2
既然数学方法可以得到2个的解，那么如何由2个推到3个呢？
笔者为此考虑了很久，列了许多数据，依然找不到好的数学递推法。因为第i个物体的上限值与i＋1个时没有必然联系。想想是显然的：
我们只是知道上限，但不知道那些不能构成的数有什么特征。比方说如果这些数都可以被7整除，那么只要还有个7的元素就可以充满，但是这对下一阶段的递推是不可见的！
穿插一点作料。这几天恰逢我们原来的电脑室network系统有问题上不了网，只得去和高一最新的基础班一起混在第二个室，那里病毒超级多∼我都没法专心写题。听着Y说“怎么生孩子”“生了几个孩子”“孩子他爸是谁”“老了不会生孩子了”“不会生了就退出了”之类的BFS的讲解∼一直听到下课离开时灵光一现：
既然两个元素的最大上限不大于
256*256-256-256
也就是大概65536的水平（2^16），那么有n个时这个上限不可能更大。于是实际上只需要考虑这0-65536的容量是不是可以用n种物品填充就可以了∼于是转化为一个V＝70000 n＝10的“完全装箱”问题。
{
TASK: nuggets
LANG: PASCAL
ID: awesome5
}
//for tripley
//by phoeagon
//2009-1-4
//dp
//beef mcnuggets
var
tt:Array[0..10]of longint;
dp:Array[0..70000]of boolean;
min,n:longint;
procedure init;
var
i:longint;
begin
reaD(n);
min:=maxlongint;
for i:=1 to n do
begin
reaD(tt[i]);
if tt[i]<min then
min:=tt[i];
end;
end;
procedure work;
var
i,j,k:longint;
begin
dp[0]:=true;
for i:=1 to n do
for j:=tt[i]to 70000 do
if dp[j-tt[i]]then
dp[j]:=true;
j:=0;
for i:=1 to 70000 do
if dp[i]then
begin
inc(j);
if j>=min then
begin writeln(i-min);exit;end;
end
else begin
j:=0;
end;
writeln('0');
end;
begin
assign(input,'nuggets.in');reset(input);
assign(output,'nuggets.out');rewrite(output);
init;
work;
close(input);close(output);
end.
如果有n种物品，单个包装的最大值为y，复杂度是O(ny^2)。在题目所给的条件下算出来大概是很囧的七十万多，对现在的电脑完全是sb。如果这样的算法能写tle的话也是您的造化。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
USER: zero judge [awesome5]
TASK: nuggets
LANG: PASCAL
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.011 secs, 272 KB]
Test 2: TEST OK [0.000 secs, 276 KB]
Test 3: TEST OK [0.000 secs, 276 KB]
Test 4: TEST OK [0.000 secs, 276 KB]
Test 5: TEST OK [0.000 secs, 276 KB]
Test 6: TEST OK [0.000 secs, 272 KB]
Test 7: TEST OK [0.000 secs, 272 KB]
All tests OK.
YOUR PROGRAM ('nuggets') WORKED FIRST TIME! That's fantastic
-- and a rare thing. Please accept these special automated
congratulations.
Here are the test data inputs:
------- test 1 -------
3
3
6
10
------- test 2 -------
2
2
3
------- test 3 -------
1
1
------- test 4 -------
4
252
250
254
256
------- test 5 -------
2
255
254
------- test 6 -------
5
251
252
250
254
256
------- test 7 -------
10
238
240
242
244
246
248
250
252
254
255
Keep up the good work!
Thanks for your submission!
至此，题目完美解决，大有 山重水复疑无路，柳暗花明又一村 的感觉。USACO的题目许多就好在能与如此让人大彻大悟的境界。
| 
