• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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 閱讀(646) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm 、USACO動態規劃

            導航

            <2009年6月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            統計

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            精品九九久久国内精品| 老司机国内精品久久久久| 久久精品无码一区二区日韩AV| 久久久国产精品| 色欲综合久久躁天天躁蜜桃| 2020最新久久久视精品爱| 久久一本综合| 久久精品国产91久久综合麻豆自制| 久久精品国产色蜜蜜麻豆| A级毛片无码久久精品免费| 久久中文字幕一区二区| 99久久99久久精品国产片果冻| 欧美日韩中文字幕久久伊人| 国产精品久久新婚兰兰| 精品免费久久久久国产一区| 无码人妻久久一区二区三区 | 狠狠色婷婷久久综合频道日韩 | 久久综合色区| 嫩草影院久久国产精品| 无码国产69精品久久久久网站| segui久久国产精品| 久久精品草草草| 久久精品国产亚洲77777| 2021国产精品久久精品| 欧美激情精品久久久久久久| 精品久久久久久99人妻| 久久se精品一区二区| 97久久久精品综合88久久| 日韩AV无码久久一区二区| 亚洲精品无码专区久久同性男| 精品久久久久久国产三级| 久久99国产精品久久99| 国产精品一久久香蕉国产线看观看 | 日韩久久久久中文字幕人妻| 国产精品九九久久精品女同亚洲欧美日韩综合区| 久久99九九国产免费看小说| 久久久亚洲欧洲日产国码是AV| 久久只有这精品99| 亚洲国产美女精品久久久久∴| 中文字幕久久久久人妻| 久久久久久国产精品免费无码|