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

            糯米

            TI DaVinci, gstreamer, ffmpeg
            隨筆 - 167, 文章 - 0, 評論 - 47, 引用 - 0
            數據加載中……

            POJ 2184 Cow Exhibition 背包

            題目大意:
            有100頭牛,每頭牛有Fi, Si兩個值。Fi, Si 范圍是-1000~1000
            選出一些牛,確保這些牛的 Sum{Fi} + Sum{Si} 最大 
            同時 Sum{Fi},Sum{Si} 都不能為負

            思路:
            一開始看到范圍那么大,首先就否決背包了!想了一個不大靈光的解法,結果wa啦。。
            后來看了Discuss。發現都是用背包過的,是最簡單的一維背包!居然還有人是搜索過的!
            但是,如果數據bt點的話,背包是不可能過的!但是USACO的題目感覺數據都弱一點,哈哈!

            代碼爛,63ms

            #include <stdio.h>

            struct {
                
            int val, used;
            }
             _slot[100024*2], *slot = &_slot[100024];
            int up, down;

            int main()
            {
                
            int n, s, f, i;

                freopen(
            "e:\\test\\in.txt""r", stdin);

                scanf(
            "%d"&n);
                up 
            = down = 0;
                
            while (n--{
                    scanf(
            "%d%d"&s, &f);
                    
            if (s < 0 && f < 0)
                        
            continue;
                    
            if (s < 0{
                        
            for (i = down; i <= up; i++{
                            
            if (!slot[i].used)
                                
            continue;
                            
            if (!slot[i + s].used || f + slot[i].val > slot[i + s].val) {
                                slot[i 
            + s].used = 1;
                                slot[i 
            + s].val = f + slot[i].val;
                            }

                        }

                        down 
            += s;
                    }
             else {
                        
            for (i = up; i >= down; i--{
                            
            if (!slot[i].used)
                                
            continue;
                            
            if (!slot[i + s].used || f + slot[i].val > slot[i + s].val) {
                                slot[i 
            + s].used = 1;
                                slot[i 
            + s].val = f + slot[i].val;
                            }

                        }

                        up 
            += s;
                    }

                    
            if (!slot[s].used || slot[s].val < f) {
                        slot[s].used 
            = 1;
                        slot[s].val 
            = f;
                    }

                }


                s 
            = 0;
                
            for (i = 0; i <= up; i++{
                    
            if (slot[i].used && slot[i].val >= 0 && slot[i].val + i > s)
                        s 
            = slot[i].val + i;
                }

                printf(
            "%d\n", s);
                
                
            return 0;
            }


            posted on 2010-02-16 10:59 糯米 閱讀(846) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            www.久久热| 久久亚洲中文字幕精品有坂深雪 | 2021国内精品久久久久久影院| 久久久久久久91精品免费观看| 好久久免费视频高清| 久久久久亚洲AV成人片| 精品综合久久久久久97| 久久国产精品无| 久久久久青草线蕉综合超碰| 伊人精品久久久久7777| 91精品国产高清91久久久久久| 人妻精品久久无码专区精东影业| 人妻久久久一区二区三区| 久久久久国产精品熟女影院| 成人资源影音先锋久久资源网| 久久精品国产秦先生| 国产精品久久久久一区二区三区| 久久精品这里只有精99品| 亚洲国产成人久久综合碰| 亚洲乱码精品久久久久.. | 久久亚洲私人国产精品vA| A狠狠久久蜜臀婷色中文网| 国产免费久久久久久无码| 亚洲国产成人久久精品99| 久久久久久夜精品精品免费啦| 久久久精品免费国产四虎| 久久青青草原精品国产不卡| 亚洲国产精品久久久天堂| 色综合色天天久久婷婷基地| 亚洲AV伊人久久青青草原| 久久午夜无码鲁丝片| 久久91这里精品国产2020| 一本久久a久久精品vr综合| 伊人热人久久中文字幕| 97精品依人久久久大香线蕉97| 99久久精品国产一区二区蜜芽| 久久精品国产亚洲αv忘忧草 | 亚洲色大成网站www久久九| 国产综合久久久久| 久久中文字幕人妻丝袜| 91久久成人免费|