• <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 | 91精品国产91久久综合| 久久亚洲AV无码西西人体| 久久国产成人| 7777久久久国产精品消防器材| 久久精品国产亚洲AV久| 精品久久久久久中文字幕人妻最新| 久久精品亚洲精品国产色婷 | 97久久精品午夜一区二区| 好久久免费视频高清| 久久精品亚洲欧美日韩久久| 欧美激情一区二区久久久| 精品熟女少妇av免费久久| 久久性生大片免费观看性| 91精品国产综合久久精品| 欧美久久综合九色综合| 日产精品久久久一区二区| 久久国产成人精品国产成人亚洲| 亚洲午夜久久久久久噜噜噜| 久久精品国产精品亚洲| 久久国产精品成人片免费| 亚洲精品无码久久久| 2020最新久久久视精品爱| 亚洲精品乱码久久久久久蜜桃不卡| 色噜噜狠狠先锋影音久久| 精产国品久久一二三产区区别 | 久久精品亚洲AV久久久无码| 亚洲国产精品久久久久婷婷软件 | 欧美大香线蕉线伊人久久| 欧美与黑人午夜性猛交久久久| 97久久国产亚洲精品超碰热| 亚洲午夜精品久久久久久浪潮| 国产美女久久精品香蕉69| 久久久久久精品无码人妻| 久久久黄色大片| 人人狠狠综合88综合久久| 精品久久久久久无码中文野结衣| 久久99精品国产99久久6男男| 久久久亚洲AV波多野结衣| 伊人久久大香线蕉无码麻豆| 欧洲性大片xxxxx久久久|