• <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 1945 Power Hungry Cows 終極打表

            這道題是一道智力題
            所以想了n久,都想不出什么“數學方法”。甚至都想不出什么比較好的剪枝方法。
            測了一下,普通的bfs比較慢。算到18步就開始就龜速了。
            要算到21步才能得出1~20000的每一個答案。然而算到21步,在T8100 cpu的本本上都要跑半分鐘,囧。。
            所以沒辦法了,只能打表了。看了一下status。發現排在第一頁的人打表的不少呢!哈哈。

            但是問題來了。20000大小的數組,每個元素在1~21之間,如果這樣表示出來
            int arr = {1, 2, 3, ....}
            那不得40k+左右嗎。顯然poj是不允許提交這么大的代碼的!
            但是status里面那些打表的人,代碼都在20k~30k左右。這是怎么回事呢?
            我有點懷疑別人看了答案,呵呵。但又不排除有方法能把代碼長度控制好。
            所以,考慮了下面幾個方法:


            1. 元素的范圍是在 1~21 之間。所以要盡量用4bit表示一個元素。
            統計了下,發現16以上的元素占了70%左右。所以規定:
            >=16的元素,表示為 u4 arr[] = { (val&0xf) + 1 } 占用4bit
            < 16的元素,表示為 u4 arr[] = { 0, val } 占用8bit
            將它稱之為"halfbyte"壓縮
            2. 霍夫曼壓縮,lz77壓縮
            3. base64編碼

            這兩天實在是閑的蛋疼。于是就把這個幾個玩意寫了一下。
            經過測試,發現用 lz77 是獲得的代碼長度是最短的!僅9k!
            統計如下:

            === generate: e:\test\1945_base64.cpp
            base64 encode: 20032 -> 26712 133.35%
            total: 20032 -> 26712 133.35%
            file size: 27.22K

            === generate: e:\test\1945_halfbyte_base64.cpp
            halfbyte encode: 20032 -> 11842 59.12%
            base64 encode: 11842 -> 15792 133.36%
            total: 20032 -> 15792 78.83%
            file size: 17.15K

            === generate: e:\test\1945_halfbyte_huffman_base64.cpp
            halfbyte encode: 20032 -> 11842 59.12%
            huffman encode: 11842 -> 5964 50.36%
            base64 encode: 5964 -> 7952 133.33%
            total: 20032 -> 7952 39.70%
            file size: 11.42K

            === generate: e:\test\1945_halfbyte_huffman_lz77_base64.cpp
            halfbyte encode: 20032 -> 11842 59.12%
            huffman encode: 11842 -> 5964 50.36%
            lz77 encode: 5964 -> 8838 148.19%
            base64 encode: 8838 -> 11784 133.33%
            total: 20032 -> 11784 58.83%
            file size: 15.78K

            === generate: e:\test\1945_huffman_base64.cpp
            huffman encode: 20032 -> 6644 33.17%
            base64 encode: 6644 -> 8860 133.35%
            total: 20032 -> 8860 44.23%
            file size: 11.71K

            === generate: e:\test\1945_huffman_lz77_base64.cpp
            huffman encode: 20032 -> 6644 33.17%
            lz77 encode: 6644 -> 8097 121.87%
            base64 encode: 8097 -> 10796 133.33%
            total: 20032 -> 10796 53.89%
            file size: 14.21K

            === generate: e:\test\1945_lz77_base64.cpp
            lz77 encode: 20032 -> 5422 27.07%
            base64 encode: 5422 -> 7232 133.38%
            total: 20032 -> 7232 36.10%
            file size: 8.81K

            所有方法都是0~32ms AC。
            呵呵,代碼太長了,就不貼了,給個下載:

            /Files/varg-vikernes/1945.rar

            posted on 2010-02-18 16:53 糯米 閱讀(2811) 評論(2)  編輯 收藏 引用 所屬分類: POJ

            評論

            # re: POJ 1945 Power Hungry Cows 終極打表[未登錄]  回復  更多評論   

            http://m.shnenglu.com/varg-vikernes/archive/2010/02/18/108024.aspx
            2014-07-30 16:07 | 糯米

            # re: POJ 1945 Power Hungry Cows 終極打表[未登錄]  回復  更多評論   

            http://blog.csdn.net/lencle/article/details/7005546
            2014-07-30 16:08 | 糯米
            99999久久久久久亚洲| 欧美国产成人久久精品| 日韩av无码久久精品免费| 久久不见久久见免费视频7| 久久人做人爽一区二区三区 | 区久久AAA片69亚洲| 久久91精品国产91| 久久777国产线看观看精品| 久久久久久久久久久免费精品| 久久精品18| 久久无码国产专区精品| 99热成人精品免费久久| 亚洲中文字幕无码一久久区| 久久成人国产精品| 麻豆av久久av盛宴av| 嫩草影院久久99| 亚洲精品乱码久久久久久蜜桃图片| 99久久人人爽亚洲精品美女| 香蕉99久久国产综合精品宅男自 | 国产精品九九久久精品女同亚洲欧美日韩综合区 | 97久久超碰成人精品网站| 久久久久成人精品无码| 久久婷婷久久一区二区三区| 久久久精品人妻一区二区三区蜜桃 | 久久亚洲精品国产精品| 99久久国产综合精品网成人影院| 99久久精品免费看国产一区二区三区 | 国产精品成人久久久| 97精品伊人久久久大香线蕉| 亚洲国产精品无码久久久不卡| 精品综合久久久久久88小说| 麻豆成人久久精品二区三区免费| 久久夜色精品国产www| 久久w5ww成w人免费| 伊人久久大香线蕉AV色婷婷色| 超级97碰碰碰碰久久久久最新 | 综合网日日天干夜夜久久| 国产精品亚洲综合专区片高清久久久| 亚洲狠狠婷婷综合久久蜜芽| 久久99精品国产麻豆蜜芽| 久久99精品久久久久久水蜜桃|