USACO 4.1 Beef McNuggets

这题有些难。虽然知道是动态规划题,但是不知道要开多大的数组,后来看analysis用一个256大小的数组循环使用,方法很巧妙。
先将box进行排序。
如果box里面的数的最大公约数不为1的话,那么所有组成的数,只可能是这个公约数的倍数,因此没有上限,输出为0.
用last记录最小的“不能组成的数”。这样当last之后有boxs[0]个连续数都可以组成的话,那么所有的数都可以组成。
last+1...last+box[0]可以组成的话,那么每个数都加一个box[0],那么新一轮的box[0]个数也可以组成,以此类推。

#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

posted on 2009-07-12 14:58 YZY 阅读(609) 评论(0)  编辑 收藏 引用 所属分类: AlgorithmUSACO动态规划


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

统计

常用链接

留言簿(2)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜