【題目描述】

農夫布朗的奶牛們正在進行斗爭，因為它們聽說麥當勞正在考慮引進一種新產品：麥香牛塊。奶牛們正在想盡一切辦法讓這種可怕的設想泡湯。奶牛們進行斗爭的策略之一是“劣質的包裝”。“看，”奶牛們說，“如果你只用一次能裝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。

【解題報告】

蛋碎的一個題。

引理：對于2個自然數q,p，若gcd(q,p)=1，則不能用xq+yp（x，y為任意自然數）的最大數為q*p-q-p。

1 {
2 ID:wwzhwdw1
3 PROG:nuggets
4 LANG:PASCAL
5 }
6 program nuggets;
7 var
8 maxn,j,n,i:longint;
9 a:array[0..11]of longint;
10 f:array[0..90000]of boolean;
11
12 procedure init;
13 begin
14 assign(input,'nuggets.in');
15 reset(input);
16 assign(output,'nuggets.out');
17 rewrite(output);
18 end;
19
20 procedure outit;
21 begin
22 halt;
23 close(input);
24 close(output);
25 end;
26
27 function min(a,b:longint):longint;
28 begin
29 if a<b then exit(a);
30 exit(b);
31 end;
32
33 function gcd(a,b:longint):longint;
34 begin
35 if b=0 then gcd:=a
36 else
37 gcd:=gcd(b,a mod b);
38 end;
39
40 procedure main;
41 begin
42 readln(n);
43 for i:=1 to n do
44 begin
45 readln(a[i]);
46 if a[i]=1 then
47 begin
48 writeln(0);
49 outit;
50 end;
51 end;
52 maxn:=maxlongint;
53 for i:=1 to n-1 do
54 for j:=i+1 to n do
55 begin
56 if gcd(a[i],a[j])=1 then maxn:=min(maxn,a[i]*a[j]-a[i]-a[j]);
57 end;
58 if maxn=maxlongint then
59 begin
60 writeln(0);
61 outit;
62 end;
63 fillchar(f,sizeof(f),0);
64 f[0]:=true;
65 for i:=1 to n do
66 for j:=a[i] to maxn do if f[j-a[i]] then f[j]:=true;
67 for i:=maxn downto 1 do if (not f[i]) then
68 begin
69 writeln(i);
70 outit;
71 end;
72 writeln(0);
73 end;
74
75 begin
76 init;
77 main;
78 outit;
79 end.
80
81

轉載于:https://www.cnblogs.com/wwzhwdwd/archive/2011/08/27/2155576.html

總結

以上是生活随笔為你收集整理的[USACO] Beef McNuggets的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。