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

            A Za, A Za, Fighting...

            堅信:勤能補拙

            PKU 3253 Fence Repair

            問題:
            http://acm.pku.edu.cn/JudgeOnline/problem?id=3253

            思路:
            哈夫曼樹(詳見CLRS)
            這題設計的很巧妙
            理解的關鍵是: 將切割木板的過程反過來觀察,也就是將所有最終的短木板進行拼接的過程,這其實就是哈夫曼樹的構造過程
            CLRS上關于哈夫曼樹的構造是以優先級隊列為基礎的
            由于傾向于用C來寫,所以并沒有使用C++的STL(當然,這要簡單的多)
            別忘了: 目的并不是要簡單,而是要鍛煉自己的算法及數據結構基礎

            以最小堆為基礎的優先級隊列實現:
             1 #define PARENT(i) ((i-1)>>1)
             2 #define LEFT_CLD(i) ((i<<1)+1)
             3 #define RIGHT_CLD(i) ((i+1)<<1)
             4 #define SWAP(a, b) a=a+b; b=a-b; a=a-b /* tricky */
             5 int heap_size;
             6 
             7 void
             8 min_heapify(long long *heap, int i)
             9 {
            10     int min = i;
            11     int left = LEFT_CLD(i);
            12     int right = RIGHT_CLD(i);
            13     if(left<heap_size && heap[min]>heap[left])
            14         min = left;
            15     if(right<heap_size && heap[min]>heap[right])
            16         min = right;
            17     if(min != i) {
            18         SWAP(heap[i], heap[min]);
            19         min_heapify(heap, min);
            20     }
            21 }
            22 
            23 void
            24 build_min_heap(long long *heap, int length)
            25 {
            26     int i;
            27     heap_size = length;
            28     for(i=(heap_size>>1)-1; i>=0; i--)
            29         min_heapify(heap, i);
            30 }
            31 
            32 long long
            33 extract_min(long long *heap)
            34 {
            35     if(heap_size < 1) {
            36         fprintf(stderr, "heap underflow\n");
            37         exit(1);
            38     }
            39     long long rt = heap[0];
            40     SWAP(heap[0], heap[heap_size-1]);
            41     --heap_size;
            42     min_heapify(heap, 0);
            43     return rt;
            44 }
            45 
            46 void
            47 decrease_key(long long *heap, int i, long long new_key)
            48 {
            49     int c, p;
            50     if(heap[i] < new_key) {
            51         fprintf(stderr, "new key is larger than current key\n");
            52         exit(1);
            53     }
            54     heap[i] = new_key;
            55     c = i;
            56     p = PARENT(i);
            57     while(c>0 && heap[p]>heap[c]) {
            58         SWAP(heap[c], heap[p]);
            59         c = p;
            60         p = PARENT(c);
            61     }
            62 }
            63 
            64 void
            65 insert(long long *heap, long long value)
            66 {
            67     ++heap_size;
            68     heap[heap_size-1= MAX_INT;
            69     decrease_key(heap, heap_size-1, value);
            70 }

            哈夫曼樹的構造(這里是簡化版,根據題意只需要計算cost即可):
             1 long long
             2 huffman_tree_way(long long *heap, int length)
             3 {
             4     int i;
             5     long long fst, snd, sum, rt=0;
             6     build_min_heap(heap, length);
             7     for(i=0; i<length-1; i++) {
             8         fst = extract_min(heap);
             9         snd = extract_min(heap);
            10         sum = fst + snd;
            11         rt += sum;
            12         insert(heap, sum);
            13     }
            14     return rt;
            15 }




            posted on 2010-07-04 10:39 simplyzhao 閱讀(302) 評論(0)  編輯 收藏 引用 所屬分類: E_數據結構

            導航

            <2010年7月>
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            2020久久精品国产免费| 久久久这里有精品| 91超碰碰碰碰久久久久久综合| 久久丫精品国产亚洲av不卡 | 性欧美大战久久久久久久| 久久人人爽人人爽AV片| 久久国产欧美日韩精品| 欧洲精品久久久av无码电影| 久久精品国产秦先生| 久久久久国产精品人妻 | 欧美精品丝袜久久久中文字幕| 亚洲?V乱码久久精品蜜桃| 久久婷婷五月综合色高清| 国内精品久久久久国产盗摄| 国内精品久久久久| 久久精品国产亚洲AV久| 亚洲国产成人久久笫一页| 亚洲国产精品久久久久网站| 欧美精品国产综合久久| 国内精品久久久久久麻豆| 久久福利青草精品资源站免费| 久久亚洲中文字幕精品有坂深雪| 久久久久综合国产欧美一区二区| 99国内精品久久久久久久| 91久久精品国产成人久久| 欧美精品一本久久男人的天堂| 91精品国产9l久久久久| 国产精品女同一区二区久久| 久久精品国产免费| 久久只有这里有精品4| 综合人妻久久一区二区精品| 国产成人精品白浆久久69| 曰曰摸天天摸人人看久久久| 99久久精品国产一区二区三区| 无码任你躁久久久久久老妇| 久久精品国产色蜜蜜麻豆| 久久亚洲电影| 99久久综合国产精品二区| 久久亚洲AV无码精品色午夜 | 蜜臀av性久久久久蜜臀aⅴ| 色综合久久综合网观看|