• <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 1171 Letter Game 背包

            思路:

            它的要求是,給你幾個字母,用這些字母拼幾個字典里面有的單詞,所有單詞加起來求最高得分。
            轉化一下,就是個01背包問題。
            由于單詞的長度很短很短了,只有3~7個字母,所以總狀態數很少啦。數組開到 2048 就可以AC了。

            后來又搜了一下別人的解題報告哦,發現有個哥們很牛逼。
            他說:單詞長度范圍在3--7內。所以可能的詞組 只能是 3+3 或 3+4

            一語驚醒腦殘人。太牛逼了!

            代碼 150ms AC。

            #include <stdio.h>

            char key[] = {
                
            "qwertyuiop"
                
            "asdfghjkl"
                
            "zxcvbnm"
            }
            ;
            int score[] = {
                
            7612254135,
                
            214655763,
                
            7746525
            }
            ;

            int map[256], col[256], idx[256], mul[8], tot[8], cnt, hash[2048], top;

            int can_add(int a, int b)
            {
                
            int i, ia, ib;

                
            for (i = 1; i < cnt; i++{
                    ia 
            = (a / mul[i - 1]) % tot[i];
                    ib 
            = (b / mul[i - 1]) % tot[i];
                    
            if (ia + ib >= tot[i])
                        
            return 0;
                }


                
            return 1;
            }


            int main()
            {
                
            int i, val, sum[256], sc;
                
            char str[16];

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

                
            for (i = 0; i < 26; i++)
                    map[key[i]] 
            = score[i];
                
                scanf(
            "%s", str);
                
            for (i = 0; str[i]; i++)
                    col[str[i]]
            ++;

                cnt 
            = 1;
                
            for (i = 'a'; i <= 'z'; i++)
                    
            if (col[i]) {
                        idx[i] 
            = cnt;
                        mul[cnt] 
            = tot[cnt] = col[i] + 1;
                        cnt
            ++;
                    }


                mul[
            0= 1;
                
            for (i = 1; i < cnt; i++)
                    mul[i] 
            *= mul[i - 1];
                top 
            = mul[cnt - 1];
                hash[
            0= 1;

                
            while (scanf("%s", str), str[0!= '.'{
                    
            for (i = 'a'; i <= 'z'; i++)
                        sum[i] 
            = 0;
                    sc 
            = 0;
                    val 
            = 0;
                    
            for (i = 0; str[i]; i++{
                        sum[str[i]]
            ++;
                        
            if (sum[str[i]] > col[str[i]])
                            
            break;
                        sc 
            += map[str[i]];
                        val 
            += mul[idx[str[i]] - 1];
                    }

                    
            if (str[i])
                        
            continue;
                    
            for (i = top; i >= 0; i--{
                        
            if (!hash[i])
                            
            continue;
                        
            if (can_add(i, val) && hash[i + val] < hash[i] + sc)
                            hash[i 
            + val] = hash[i] + sc;
                    }

                }


                sc 
            = 0;
                
            for (i = top; i >= 0; i--)
                    
            if (hash[i] > sc)
                        sc 
            = hash[i];
                printf(
            "%d\n", sc - 1);

                
            return 0;
            }

            posted on 2010-05-10 21:37 糯米 閱讀(512) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            亚洲欧美另类日本久久国产真实乱对白| 久久精品中文闷骚内射| 久久亚洲私人国产精品| 亚洲午夜无码久久久久| 亚洲国产精品无码久久SM| 久久国产精品国产自线拍免费| 99精品伊人久久久大香线蕉| 久久久久亚洲精品天堂久久久久久| 色婷婷久久久SWAG精品| 色欲综合久久躁天天躁蜜桃| 成人资源影音先锋久久资源网| 日批日出水久久亚洲精品tv| 久久成人国产精品免费软件| 久久99久久无码毛片一区二区| 国内精品久久久久影院薰衣草| 久久精品国产亚洲AV无码麻豆| 超级碰久久免费公开视频| 久久se精品一区精品二区| 久久www免费人成看国产片| 亚洲va久久久噜噜噜久久男同 | 精品久久国产一区二区三区香蕉| 久久影院亚洲一区| 91精品国产综合久久久久久| 色偷偷88欧美精品久久久| 亚洲综合婷婷久久| 蜜臀久久99精品久久久久久小说| 久久人人爽人人澡人人高潮AV| 精品国产91久久久久久久| 麻豆精品久久久久久久99蜜桃| 中文字幕精品无码久久久久久3D日动漫| 久久综合给合久久狠狠狠97色69| 久久久99精品成人片中文字幕| 久久精品亚洲男人的天堂| 久久99精品国产| 狠狠狠色丁香婷婷综合久久五月| 亚洲精品国产美女久久久| 久久综合久久综合亚洲| 色欲综合久久躁天天躁| 久久99精品久久久久久齐齐| 国产高潮国产高潮久久久91| 久久九九有精品国产23百花影院|