國家集訓(xùn)隊2005論文集 楊弋

《國家集訓(xùn)隊2005論文集 楊弋》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、從《小H的小屋》的解法談算法的優(yōu)化安徽師范大學(xué)附屬中學(xué)楊弋題目大意小H有一個院子，東西方向長為100單位。東墻和西墻均平行于y軸，北墻和南墻分別是斜率為k1和k2的直線。北墻和南墻分別圍有多塊草坪，每塊草坪都是一個矩形，矩形的每條邊都平行于坐標(biāo)軸。相鄰兩塊草坪的接觸點恰好在墻上，接觸點的橫坐標(biāo)被稱為它所在墻的“分點”，這些分點必須是1到99的整數(shù)。北墻要有m塊草坪，南墻要有n塊草坪，并約定，m≤n。如果記北墻和南墻的分點集合分別為X1,X2，則應(yīng)滿足X1X2。輸入k1，k2，m，n。k1和k2為正實數(shù)，m和n為正整數(shù)，且2≤m≤n≤100。假定南北墻距離很遠(yuǎn)，南墻草坪

2、和北墻草坪不會重疊。題目大意讓我們來看一個例子：輸入：0.50.224圖中給出的就是這組數(shù)據(jù)的最優(yōu)解，最小面積為3000。yx西東南北0255075100算法一看到題目，我們首先想到的算法是動態(tài)規(guī)劃。我們用f(w,u,v)表示長度為w，北墻u塊草坪和南墻v塊草坪時的最小面積。令一塊北墻草坪和其對應(yīng)的南墻草坪為一個“塊”，若北墻草坪長度為x，南墻草坪塊數(shù)為k，則該塊最小面積為area(x,k)。f(w,u,v)=min{f(w-x,u-1,v-k)+area(x,k)}x共k塊…………算法一這樣，我們就得到了算法一：1、枚舉所有合法的w,u,v，對于每一組w,u,v,計

3、算f(w,u,v)。2、在計算f(w,u,v)時，枚舉所有合法的x,k，從而求出f(w,u,v)。3、f(100,m,n)就是我們所要求的解。該算法時間復(fù)雜度是O(l2mn2)空間復(fù)雜度是O(ln)太慢了！算法一看來，我們必須優(yōu)化我們的算法……算法二在狀態(tài)轉(zhuǎn)移時，假如我們已經(jīng)確定了x……kf(w,u,v)kakkb時曲線是上升的kb算法二我們枚舉x，當(dāng)x增大的時候，ka不會減小。這樣，我們可以枚舉x的同時計算ka。由于x和ka都是遞增的,該算法的時間復(fù)雜度降為O(l2mn)，空間復(fù)雜度仍然是O(ln)。算法二我們注意到計算f(w,u,v)的最優(yōu)

4、解所用的x,k必不小于計算f(w,u+1,v)的最優(yōu)解所用的x,k（假如f(w,u+1,v)存在的話），所以我們可以記錄計算最優(yōu)解時用的x,k，從而進(jìn)一步減少程序運行所用時間。算法二無論在時間復(fù)雜度上還是在空間復(fù)雜度上都足夠應(yīng)付這道題目的所有數(shù)據(jù)了。那么，究竟有沒有更好的方法呢？算法三現(xiàn)在讓我們徹底拋棄動態(tài)規(guī)劃的思想，來試一試貪心算法在此題中的應(yīng)用。100Hil5050252550北墻草坪南墻草坪k1=k2=1,m=2,n=3我們盡可能平均地分配北墻草坪的長度然后再盡可能平均地為南墻草坪分配長度S=87505050252550算法三100Hil5743292843北

5、墻草坪南墻草坪k1=k2=1,m=2,n=3但是……S=8572這樣的貪心算法是錯誤的!算法三為什么說這個貪心算法是錯誤的？因為每一塊北墻草坪對應(yīng)的南墻草坪數(shù)量并不是相等的！如果我們能使每一塊北墻草坪對應(yīng)的南墻草坪數(shù)量相等……顯然，這時盡量平均分配得到的就是最優(yōu)解了北墻草坪南墻草坪算法三現(xiàn)在我們假設(shè)最優(yōu)解有這樣的情況北墻草坪對應(yīng)的南墻草坪塊數(shù)的差距大于1了。算法三那么……總存在這樣的調(diào)整，調(diào)整以后差距會小于等于1，并且總面積不會比原來大。我們可以把南墻草坪按塊數(shù)盡可能平均地分配給北墻草坪！算法三這里是一個例子我們有3塊北墻草坪和10塊南墻草坪，該怎么分配呢？算法三我們

6、先把整個墻分成兩部分，第一部分包含m1段北墻草坪，每段對應(yīng)n1段南墻草坪；第二部分包含m2段北墻草坪，每段對應(yīng)n2段南墻草坪。如果兩部分的長度確定了，在兩部分內(nèi)，都可以直接貪心求該部分的最小面積。我們枚舉其中一個部分的長度，另一個部分的總長度也就確定了，此時的最優(yōu)解可以在O(1)時間內(nèi)計算出來。于是，我們得到了一個全新的算法：算法三就像這樣：這樣，整個算法的時間復(fù)雜度是O(l-n)的，空間復(fù)雜度是O(1)的。算法四我們的優(yōu)化還沒有結(jié)束！現(xiàn)在讓我們來看看算法四吧我們設(shè)分給第一部分的東西向長度為i。設(shè)能使S取到最優(yōu)解的最小i為i1，能使S取到最優(yōu)解的最大i為i2。和我們在

7、思考算法二時的情況類似，我們發(fā)現(xiàn)ii2時S隨i增大而增大，在i1≤i≤i2時S始終能取到最小值。算法四就像這樣iSi1i