• <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的最優操作序列),那么答案就是這兩個序列的最有配對,顯然最大配最小這樣的順序可得到最優解。
            欧美日韩中文字幕久久伊人| 久久这里都是精品| 9久久9久久精品| 精品一区二区久久| 久久男人AV资源网站| 一本色道久久综合狠狠躁篇| 久久精品国产亚洲αv忘忧草| 亚洲国产精品无码久久98| 99久久99久久久精品齐齐| 久久久久亚洲?V成人无码| 亚洲中文字幕无码久久综合网| 91精品国产91久久综合| 亚洲国产精品无码久久青草| 国产午夜福利精品久久2021| 久久久久亚洲av毛片大| 久久精品无码专区免费青青| 亚洲欧洲精品成人久久曰影片 | 久久99精品久久只有精品| 99久久国产免费福利| 亚洲va久久久噜噜噜久久| 国产精品免费久久| 国产精品免费福利久久| 亚洲熟妇无码另类久久久| 久久免费视频一区| 97久久精品人人澡人人爽| 狼狼综合久久久久综合网| 久久天天躁狠狠躁夜夜不卡| 国产L精品国产亚洲区久久| 久久99亚洲网美利坚合众国| 色综合久久中文字幕无码| 欧美日韩精品久久久久 | 亚洲综合熟女久久久30p| 久久久精品久久久久久| 国产ww久久久久久久久久| 久久本道伊人久久| 国产精品久久久久久久久免费| 亚洲国产另类久久久精品| 久久婷婷国产综合精品| 青草国产精品久久久久久| 久久久老熟女一区二区三区| 日韩精品久久无码中文字幕|