• <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 1170 Shopping Offers 動態規劃

            思路:

            由于一共有5種物品,每種物品最多只能有5個,所以物品的擁有情況,可以表示為 6*6*6*6*6 中狀態。
            這個數好像是 7k 多,不大。
            狀態轉移發生在有折扣的時候,如果當前的狀態可以打折,那么就看打折之后是否會比現在劃算就可以了。

            一開始用的是取模,后來改成位操作了,快了一點,但還是很慢,不明白那些0ms怎么來的,⊙﹏⊙b汗
            代碼很爛,僅供參考

            #include <stdio.h>

            int S, B;
            int price[1024], code[1024];
            int offer[128], cut[128];
            int ans[1 << 15];

            inline 
            int min(int a, int b)
            {
                
            return a < b ? a : b;
            }


            int main()
            {
                
            int c, k, i, j, n, t, m[5], a, b;

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

                scanf(
            "%d"&B);
                t 
            = 0;
                
            for (i = 0; i < B; i++{
                    scanf(
            "%d%d%d"&c, &k, &price[i]);
                    t 
            |= k << (i*3);
                    code[c] 
            = i;
                }

                scanf(
            "%d"&S);
                
            for (i = 0; i < S; i++{
                    scanf(
            "%d"&n);
                    offer[i] 
            = 0;
                    
            while (n--{
                        scanf(
            "%d%d"&c, &k);
                        offer[i] 
            |= k << (code[c]*3);
                    }

                    scanf(
            "%d"&cut[i]);
                }

                
            for (i = 0; i <= t; i++{
                    ans[i] 
            = 0;
                    a 
            = i;
                    
            for (j = 0; j < B; j++{
                        ans[i] 
            += price[j] * (a & 7);
                        a 
            >>= 3;
                    }

                    
            for (j = 0; j < S; j++{
                        a 
            = i;
                        b 
            = offer[j];
                        
            for (k = 0; k < B; k++{
                            
            if ((a & 7< (b & 7))
                                
            break;
                            a 
            >>= 3;
                            b 
            >>= 3;
                        }

                        
            if (k < B)
                            
            continue;
                         ans[i] 
            = min(ans[i], ans[i - offer[j]] + cut[j]);
                    }

                }

                printf(
            "%d\n", ans[t]);

                
            return 0;
            }


            posted on 2010-04-21 21:32 糯米 閱讀(488) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            久久青青草原国产精品免费| 国内精品久久久久久不卡影院| 久久国产福利免费| 欧美日韩精品久久久久| 99久久精品免费看国产一区二区三区 | 国产综合精品久久亚洲| 精品99久久aaa一级毛片| 婷婷久久五月天| 久久国产高潮流白浆免费观看| 国产亚洲成人久久| 亚洲欧洲日产国码无码久久99| 久久福利青草精品资源站免费| 久久综合五月丁香久久激情| 亚洲精品无码久久久久| 97久久精品无码一区二区| 久久久久99精品成人片| 狠狠色丁香久久婷婷综| 久久久久久国产精品无码下载| 国产精品久久影院| 亚洲va国产va天堂va久久| 精品熟女少妇aⅴ免费久久| 久久精品国产亚洲AV电影| 性欧美大战久久久久久久| AAA级久久久精品无码区| 久久超乳爆乳中文字幕| 亚洲一区精品伊人久久伊人| 亚洲国产精品久久久久婷婷老年| 亚洲国产精品成人久久| 久久久受www免费人成| 亚洲国产成人久久精品动漫| 久久久久久久久久久久中文字幕| 人人妻久久人人澡人人爽人人精品| 久久国产精品一区| 99久久精品国产毛片| 国内精品久久国产大陆| 久久精品免费一区二区三区| 99精品久久精品一区二区| 精品久久久久久国产潘金莲| 精品国际久久久久999波多野| 国产精品欧美久久久天天影视| 亚洲中文久久精品无码ww16|