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

            O(1) 的小樂

            Job Hunting

            公告

            記錄我的生活和工作。。。
            <2011年10月>
            2526272829301
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            統計

            • 隨筆 - 182
            • 文章 - 1
            • 評論 - 41
            • 引用 - 0

            留言簿(10)

            隨筆分類(70)

            隨筆檔案(182)

            文章檔案(1)

            如影隨形

            搜索

            •  

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            [導入]偏序集 Dilworth 定理 poj 1065 3636 1548
              在Partially order set(偏序集)有一個非常NX的定理叫Dilworth Theorem。上圖是偏序集的一個Hasse diagram,偏序集的定義是 偏序是在集合X上的二元關系≤,它滿足自反性、反對稱性和傳遞性。即,對于X中的任意元素a,b和c,有: 自反性:a≤a; 反對稱性:如果a≤b且b≤a,則有a=b; 傳遞性:如果a≤b且b≤c,則a≤c 。 帶有偏序關系的集合稱為偏序集。 令(X,≤)是一個偏序集,對于集合中的兩個元素a、b,如果有a≤b或者b≤a,則稱a和b是可比的,否則a和b不可比。 在X中,對于元素a,如果任意元素b,由b≤a得出b=a,則稱a為極小元。 一個反鏈A是X的一個子集,它的任意兩個元素都不能進行比較。 一個鏈C是X的一個子集,它的任意兩個元素都可比。 下面是兩個重要定理: 定理1 令(X,≤)是一個有限偏序集,并令r是其最大鏈的大小。則X可以被劃分成r個但不能再少的反鏈。 其對偶定理稱為Dilworth定理: 定理2 令(X,≤)是一個有限偏序集,并令m是反鏈的最大的大小。則X可以被劃分成m個但不能再少的鏈。 搞清楚了反鏈和鏈的定義,就能夠很好的從Hasse Diagram中得到理解。鏈就是從縱向的角度看 Hasse Diagram ,反鏈是從橫向的角度看Hasse Diagram。 定理一,就是至少有r行構成反鏈關系。 定理二,就是至少有m列構成鏈關系。    我們來考慮一個導彈攔截問題,就是求一個序列的最長不上升子序列,以及求能最少劃分成幾組不上升子序列。 很顯然第一個是動態規劃,動態規劃的過程就是求Hasse Diagram的過程?。。?   第二問就是求最少能夠劃分成幾個鏈,根據定理2 [...]
            文章來源:http://www.lxlsosi.tk/2011/05/26/%e5%81%8f%e5%ba%8f%e9%9b%86-dilworth-%e5%ae%9a%e7%90%86-poj-1065-3636-1548/

            posted on 2011-05-26 20:56 Sosi 閱讀(550) 評論(0)  編輯 收藏 引用

            統計系統
            久久婷婷午色综合夜啪| 久久精品国产精品青草| 久久人人爽人爽人人爽av | 伊人色综合久久天天人守人婷| 久久99国产一区二区三区| 精品国产乱码久久久久软件| 久久亚洲精品无码AV红樱桃| 久久久久国产亚洲AV麻豆| 久久这里都是精品| 88久久精品无码一区二区毛片| 亚洲精品99久久久久中文字幕| 99久久精品国产麻豆| 青春久久| 国产综合成人久久大片91| 亚洲va久久久噜噜噜久久男同| 国产ww久久久久久久久久| 亚洲愉拍99热成人精品热久久| 久久久久久久综合综合狠狠| 国产91色综合久久免费| 中文字幕人妻色偷偷久久| 久久综合伊人77777麻豆| 香港aa三级久久三级| 久久久久亚洲AV片无码下载蜜桃| 伊人久久大香线蕉综合5g| 久久国产福利免费| 久久精品国产99国产精品澳门| 久久精品国产清自在天天线| 三级韩国一区久久二区综合| 99久久国产免费福利| 日本道色综合久久影院| 国产Av激情久久无码天堂| 久久婷婷激情综合色综合俺也去| 久久中文字幕精品| 久久人人爽人人爽人人片av麻烦| 色综合久久中文字幕综合网 | 色欲综合久久躁天天躁| 久久久久久极精品久久久| 久久国产精品免费| 亚洲七七久久精品中文国产| 久久久久99这里有精品10| 亚洲国产欧洲综合997久久|