這題有些難。雖然知道是動(dòng)態(tài)規(guī)劃題，但是不知道要開多大的數(shù)組，后來看analysis用一個(gè)256大小的數(shù)組循環(huán)使用，方法很巧妙。
先將box進(jìn)行排序。
如果box里面的數(shù)的最大公約數(shù)不為1的話，那么所有組成的數(shù)，只可能是這個(gè)公約數(shù)的倍數(shù)，因此沒有上限，輸出為0.
用last記錄最小的“不能組成的數(shù)”。這樣當(dāng)last之后有boxs[0]個(gè)連續(xù)數(shù)都可以組成的話，那么所有的數(shù)都可以組成。
last+1...last+box[0]可以組成的話，那么每個(gè)數(shù)都加一個(gè)box[0],那么新一輪的box[0]個(gè)數(shù)也可以組成，以此類推。
#include?<iostream>
#include?<fstream>
using?namespace?std;
ifstream?fin("nuggets.in");
ofstream?fout("nuggets.out");
#ifdef?_DEBUG
#define?out?cout
#define?in?cin
#else
#define?out?fout
#define?in?fin
#endif
int?box_num;
int?boxs[10];
bool?ok[256];
int?gcd(int?a,int?b)
{
????if(a<b)?swap(a,b);
????int?tmp;
????while(b!=0){
????????tmp?=?a;
????????a?=?b;
????????b?=?tmp%b;
????}
????return?a;
}
void?solve()
{
????in>>box_num;
????for(int?i=0;i<box_num;++i)
????????in>>boxs[i];
????sort(&boxs[0],&boxs[box_num]);
????
????int?t?=?boxs[0];
????for(int?i=1;i<box_num;++i){
????????t?=?gcd(t,boxs[i]);
????}
????if(t!=1){
????????out<<0<<endl;
????????return;
????}
????memset(ok,0,sizeof(ok));
????int?last?=?0;
????ok[0]?=?true;
????int?i=0;
????while(true){
????????if(ok[i%256]){
????????????ok[i%256]?=?0;
????????????if(i-last>=boxs[0]){
????????????????out<<last<<endl;
????????????????return;
????????????}
????????????for(int?x=0;x<box_num;++x){
????????????????ok[(i+boxs[x])%256]?=?true;
????????????}
????????}else{
????????????last?=?i;
????????}
????????++i;
????}
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}
Beef McNuggets
Hubert Chen Farmer Brown's cows are up in arms, having heard that McDonalds is
considering the introduction of a new product: Beef McNuggets. The
cows are trying to find any possible way to put such a product in a
negative light.
One strategy the cows are pursuing is that of `inferior packaging'.
``Look,'' say the cows, ``if you have Beef McNuggets in boxes of 3, 6,
and 10, you can not satisfy a customer who wants 1, 2, 4, 5, 7, 8, 11,
14, or 17 McNuggets. Bad packaging: bad product.''
Help the cows. Given N (the number of packaging options, 1 <= N
<= 10), and a set of N positive integers (1 <= i <= 256) that
represent the number of nuggets in the various packages, output the
largest number of nuggets that can not be purchased by buying nuggets
in the given sizes. Print 0 if all possible purchases can be made or
if there is no bound to the largest number.
The largest impossible number (if it exists) will be no larger than
2,000,000,000.
PROGRAM NAME: nuggets
INPUT FORMAT
| Line 1: | N, the number of packaging options |
| Line 2..N+1: | The number of nuggets in one kind of
box |
SAMPLE INPUT (file nuggets.in)
3
3
6
10
OUTPUT FORMAT
The output file should contain a single line containing a single integer
that represents the largest number of nuggets that can not be represented
or 0 if all possible purchases can be made or if there is no bound to
the largest number.
SAMPLE OUTPUT (file nuggets.out)
17