hyf

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

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