• <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)

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            中文字幕精品无码久久久久久3D日动漫| 精品久久久久成人码免费动漫 | 国产人久久人人人人爽| 一本一本久久A久久综合精品| 日本久久久久亚洲中字幕| 99久久成人国产精品免费| 久久99精品国产麻豆蜜芽| 伊人热热久久原色播放www| 婷婷久久久亚洲欧洲日产国码AV| 色综合久久久久网| 久久久久亚洲AV成人网人人网站| 97精品国产91久久久久久| 久久精品国产99久久香蕉| 人妻精品久久久久中文字幕69| 一本久久a久久精品综合夜夜| 热久久视久久精品18| 香蕉久久夜色精品国产小说| 伊人色综合久久天天人手人婷 | 亚洲午夜精品久久久久久app| 久久无码人妻一区二区三区午夜 | 久久久久国产精品嫩草影院| 一级做a爰片久久毛片16| 伊人久久大香线蕉亚洲五月天| 精品久久久久久国产牛牛app| 久久久久亚洲av无码专区导航| 亚洲午夜久久久| 久久人人爽人人爽人人片AV东京热| 久久国产精品无码HDAV | 99久久成人18免费网站| 日本久久久久亚洲中字幕| 久久亚洲日韩看片无码| 亚洲国产一成久久精品国产成人综合 | 久久这里只有精品18| 色老头网站久久网| 久久久久久久久久久精品尤物| 久久精品国产精品亚洲艾草网美妙| 91麻精品国产91久久久久| 99久久国产综合精品成人影院| 久久久国产精品网站| 国产精品岛国久久久久| 久久国产精品久久久|