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

            USACO筆記(不定期更新)

            Posted on 2009-09-13 15:52 hyf 閱讀(380) 評論(0)  編輯 收藏 引用 所屬分類: OI
                雖然USACO已刷完,但最近遇到一些相似問題依然頻頻出錯,故在此記下一些筆記。

            09-09-13
                usaco4.2有一道工件安排的題,大概題意是n個工件需要進行處理,必須先進行操作A然后是操作B,有m1臺A機器和m2臺B機器,給出每臺機器的操作時間,要求最先完成所有工件操作A的時間和最先完成所有操作的時間。
                問題1的解法是很明顯的貪心,即每次選出能最快完成當前工件的機器,證明很簡單,從i-1到i選擇最優機器是明顯的,只需說明最優的i-1的局面對i是可以得出i的最優答案的,如果i-1有非最優局面添加一個工件可以達到更優,那么添加新工件的位置會占去一個以前的最優解位置,而以前的工件就會放到對于當時并不最優的位置上去,不會比把現在工件放到此位置更優。
                問題2的解法是按問題1的方法求出一個工件完成時間序列,然后用A大的匹配B小的這樣的順序來匹配,找出一個最大值就是答案。這個問題證明的關鍵是這樣匹配的解是否是合法的(如果是合法的那么正確性顯然),我們可以把工件的操作看成是倒著的,即先操作B再操作A,那么把操作B的部分換成B的最優操作序列顯然是合法的,因為這是A和B的操作都是合法且不會互相干擾,并且必定不會比以前的差(因為這分別是A和B的最優操作序列),那么答案就是這兩個序列的最有配對,顯然最大配最小這樣的順序可得到最優解。
            色婷婷久久久SWAG精品| 久久久久免费精品国产| 国产成人精品久久一区二区三区av | 久久久久国产一区二区| 久久久久国色AV免费看图片| 国内精品人妻无码久久久影院导航 | 国产aⅴ激情无码久久| 一本色道久久88—综合亚洲精品 | 国产成人综合久久精品尤物| 99久久人人爽亚洲精品美女| 久久久久亚洲av毛片大| 久久久久久人妻无码| 久久久午夜精品福利内容| 国产欧美久久一区二区| 久久成人小视频| 久久久这里只有精品加勒比| 久久精品人人做人人爽电影蜜月 | 亚洲精品无码久久久久久| 久久se精品一区二区| 久久99热这里只频精品6| 久久午夜电影网| 国内精品久久久久久野外| 色天使久久综合网天天| 久久影院午夜理论片无码 | 亚洲中文久久精品无码ww16| 99热精品久久只有精品| 2021少妇久久久久久久久久| 色婷婷综合久久久中文字幕| 久久精品国产亚洲AV久| 2021国内久久精品| 久久无码高潮喷水| 久久综合精品国产一区二区三区| 韩国三级中文字幕hd久久精品 | 国产成人无码精品久久久久免费 | 一本久久a久久精品vr综合| 久久99精品九九九久久婷婷| 久久综合久久久| 蜜臀久久99精品久久久久久| 久久精品国产72国产精福利| 久久噜噜久久久精品66| 亚洲国产精品嫩草影院久久|