• <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
            數(shù)據(jù)加載中……

            POJ 1171 Letter Game 背包

            思路:

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

            后來又搜了一下別人的解題報告哦,發(fā)現(xiàn)有個哥們很牛逼。
            他說:單詞長度范圍在3--7內(nèi)。所以可能的詞組 只能是 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

            久久天天躁狠狠躁夜夜网站| 久久99久国产麻精品66| 伊人色综合九久久天天蜜桃 | 亚洲国产精品无码久久98| 久久精品成人欧美大片| 久久久久高潮毛片免费全部播放 | 综合久久给合久久狠狠狠97色| 色欲综合久久躁天天躁| 久久久久久国产精品免费无码| 久久青草国产手机看片福利盒子| 久久黄视频| 99久久人妻无码精品系列| 午夜福利91久久福利| 久久天天躁狠狠躁夜夜网站| 久久夜色撩人精品国产小说| 亚洲一区中文字幕久久 | 久久ww精品w免费人成| 99久久精品久久久久久清纯| 欧美伊人久久大香线蕉综合| 久久久久亚洲精品男人的天堂| 久久无码专区国产精品发布| 久久综合狠狠综合久久激情 | 亚洲va久久久噜噜噜久久| 99久久99久久精品国产| 性欧美大战久久久久久久久| 久久免费大片| 狠狠人妻久久久久久综合| 国产激情久久久久影院老熟女免费| 久久99精品久久久久久久不卡| 欧美国产精品久久高清| 精品久久久久久久久久久久久久久 | 国产精品免费看久久久香蕉| 久久香蕉国产线看观看99| 色欲综合久久中文字幕网| 国产激情久久久久久熟女老人| 久久中文字幕人妻熟av女| 亚洲成av人片不卡无码久久| 国产亚州精品女人久久久久久 | 伊人精品久久久久7777| 久久久久亚洲AV无码专区桃色| 久久精品成人欧美大片|