hyf

    雖然USACO已刷完，但最近遇到一些相似問題依然頻頻出錯，故在此記下一些筆記。

09-09-13
    usaco4.2有一道工件安排的題，大概題意是n個工件需要進行處理，必須先進行操作A然后是操作B，有m1臺A機器和m2臺B機器，給出每臺機器的操作時間，要求最先完成所有工件操作A的時間和最先完成所有操作的時間。
    問題1的解法是很明顯的貪心，即每次選出能最快完成當(dāng)前工件的機器，證明很簡單，從i-1到i選擇最優(yōu)機器是明顯的，只需說明最優(yōu)的i-1的局面對i是可以得出i的最優(yōu)答案的，如果i-1有非最優(yōu)局面添加一個工件可以達到更優(yōu)，那么添加新工件的位置會占去一個以前的最優(yōu)解位置，而以前的工件就會放到對于當(dāng)時并不最優(yōu)的位置上去，不會比把現(xiàn)在工件放到此位置更優(yōu)。
    問題2的解法是按問題1的方法求出一個工件完成時間序列，然后用A大的匹配B小的這樣的順序來匹配，找出一個最大值就是答案。這個問題證明的關(guān)鍵是這樣匹配的解是否是合法的（如果是合法的那么正確性顯然），我們可以把工件的操作看成是倒著的，即先操作B再操作A,那么把操作B的部分換成B的最優(yōu)操作序列顯然是合法的，因為這是A和B的操作都是合法且不會互相干擾，并且必定不會比以前的差（因為這分別是A和B的最優(yōu)操作序列），那么答案就是這兩個序列的最有配對，顯然最大配最小這樣的順序可得到最優(yōu)解。