國(guó)家集訓(xùn)隊(duì)2006論文集 湯澤

《國(guó)家集訓(xùn)隊(duì)2006論文集 湯澤》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、2006年全國(guó)信息學(xué)冬令營(yíng)講座從一類(lèi)單調(diào)性問(wèn)題看算法的優(yōu)化湖南省長(zhǎng)沙市第一中學(xué)湯澤【關(guān)鍵字】數(shù)據(jù)關(guān)系隊(duì)列單調(diào)性【摘要】充分挖掘數(shù)據(jù)關(guān)系，往往是構(gòu)造出優(yōu)秀算法的關(guān)鍵因素。本文從單調(diào)性入手，詳細(xì)討論了允許在表的尾端進(jìn)行插入，而在兩端刪除元素的特殊隊(duì)列對(duì)一類(lèi)單調(diào)性問(wèn)題的優(yōu)化方法，并以此說(shuō)明充分利用數(shù)據(jù)關(guān)系對(duì)構(gòu)造優(yōu)秀算法的重要性?！菊摹繉?duì)于很多問(wèn)題，如果我們充分挖掘問(wèn)題當(dāng)中隱含的數(shù)據(jù)關(guān)系，并對(duì)某些簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)作出相應(yīng)變形，應(yīng)用于這些數(shù)據(jù)關(guān)系，就能以較低的編程復(fù)雜度來(lái)實(shí)現(xiàn)算法的優(yōu)化。本文將通過(guò)一種特殊隊(duì)列在一類(lèi)單調(diào)性問(wèn)題中的運(yùn)用，來(lái)討論這種思想的具

2、體應(yīng)用。隊(duì)列是一種我們非常熟悉的數(shù)據(jù)結(jié)構(gòu)。最常見(jiàn)的隊(duì)列是一種先進(jìn)先出的線(xiàn)性表：它只允許在表的一端進(jìn)行插入，而在另一端刪除元素。我們對(duì)這種常見(jiàn)隊(duì)列稍作變形，構(gòu)造出一個(gè)特殊隊(duì)列：它允許在表的尾端進(jìn)行插入，而在兩端刪除元素。對(duì)于一些問(wèn)題，如果能夠挖掘出問(wèn)題中隱含的單調(diào)關(guān)系，這種特殊隊(duì)列能夠很好地幫助我們完成算法的優(yōu)化。一、在動(dòng)態(tài)規(guī)劃問(wèn)題中的應(yīng)用運(yùn)用單調(diào)性和這種特殊隊(duì)列進(jìn)行優(yōu)化的例子最常見(jiàn)于動(dòng)態(tài)規(guī)劃問(wèn)題當(dāng)中。有些動(dòng)態(tài)規(guī)劃問(wèn)題，可以利用決策的單調(diào)性，運(yùn)用這種特殊隊(duì)列來(lái)實(shí)現(xiàn)“降一維”。下面是一個(gè)具體的問(wèn)題?！締?wèn)題一】鋸木場(chǎng)選址（CEOI2004）從山頂上

3、到山底下沿著一條直線(xiàn)種植了n棵老樹(shù)。當(dāng)?shù)氐恼疀Q定把他們砍下來(lái)。為了不浪費(fèi)任何一棵木材，樹(shù)被砍倒后要運(yùn)送到鋸木廠(chǎng)。112006年全國(guó)信息學(xué)冬令營(yíng)講座木材只能按照一個(gè)方向運(yùn)輸：朝山下運(yùn)。山腳下有一個(gè)鋸木廠(chǎng)。另外兩個(gè)鋸木廠(chǎng)將新修建在山路上。你必須決定在哪里修建兩個(gè)鋸木廠(chǎng)，使得傳輸?shù)馁M(fèi)用總和最小。假定運(yùn)輸每公斤木材每米需要一分錢(qián)。任務(wù)你的任務(wù)是寫(xiě)一個(gè)程序：從標(biāo)準(zhǔn)輸入讀入樹(shù)的個(gè)數(shù)和他們的重量與位置計(jì)算最小運(yùn)輸費(fèi)用將計(jì)算結(jié)果輸出到標(biāo)準(zhǔn)輸出輸入輸入的第一行為一個(gè)正整數(shù)n——樹(shù)的個(gè)數(shù)（2≤n≤20000）。樹(shù)從山頂?shù)缴侥_按照1，2……n標(biāo)號(hào)。接下來(lái)n行，每

4、行有兩個(gè)正整數(shù)（用空格分開(kāi)）。第i+1行含有：wi——第i棵樹(shù)的重量（公斤為單位）和di——第i棵樹(shù)和第i+1棵樹(shù)之間的距離，1≤wi≤10000，0≤di≤10000。最后一個(gè)數(shù)dn，表示第n棵樹(shù)到山腳的鋸木廠(chǎng)的距離。保證所有樹(shù)運(yùn)到山腳的鋸木廠(chǎng)所需要的費(fèi)用小于2000000000分。輸出輸出只有一行一個(gè)數(shù)：最小的運(yùn)輸費(fèi)用。樣例輸入9122133113216211211輸出26在解決這一問(wèn)題時(shí)，首先我們要明確，將鋸木廠(chǎng)建立在相鄰兩棵樹(shù)之間是沒(méi)有任何意義的，否則我們可以將這樣的鋸木廠(chǎng)上移到最近的一棵樹(shù)處，此時(shí)運(yùn)送上方樹(shù)木的費(fèi)用減少，運(yùn)送下方樹(shù)木

5、的費(fèi)用沒(méi)有變化，總費(fèi)用降低。為了方便討論，我們先作如下定義：112006年全國(guó)信息學(xué)冬令營(yíng)講座假設(shè)山腳鋸木場(chǎng)處也有一棵樹(shù)，編號(hào)為，并且。表示第1棵樹(shù)到第棵樹(shù)的質(zhì)量和，即。表示第1棵樹(shù)到第棵樹(shù)的距離，即。特別的，有，表示第1棵樹(shù)到自己的距離為0。表示在第棵樹(shù)處建一個(gè)鋸木廠(chǎng)，并且將第1到第棵樹(shù)全部運(yùn)往這個(gè)伐木場(chǎng)所需的費(fèi)用。顯然有。特別的，有。表示在第棵樹(shù)處建一個(gè)鋸木場(chǎng)，并且將第到第棵樹(shù)全部運(yùn)往這個(gè)鋸木場(chǎng)所需的費(fèi)用。則。特別的，當(dāng)時(shí)。綜上可知，求出所有與的時(shí)間復(fù)雜度為，此后求任意的時(shí)間復(fù)雜度都為。設(shè)表示在第棵樹(shù)處建立第二個(gè)鋸木場(chǎng)的最小費(fèi)用，則有。直

6、接用這個(gè)式子計(jì)算的時(shí)間復(fù)雜度為，由于問(wèn)題規(guī)模太大，直接使用這一算法必然超時(shí)，因此我們必須對(duì)算法進(jìn)行優(yōu)化。在討論如何進(jìn)行優(yōu)化以前，我們首先證明下面這一猜想。[猜想]如果在位置建設(shè)第二個(gè)鋸木廠(chǎng),第一個(gè)鋸木廠(chǎng)的位置是時(shí)最優(yōu)。那么如果在位置建設(shè)第二個(gè)鋸木廠(chǎng),第一個(gè)鋸木廠(chǎng)的最佳位置不會(huì)小于。證明：令表示決策變量取時(shí)的值，即。設(shè)，則有112006年全國(guó)信息學(xué)冬令營(yíng)講座若，則有將含K的項(xiàng)移到不等式左邊，整理得我們令，當(dāng)時(shí)因?yàn)椋詫?duì)于有。證畢。由上面的證明，可以說(shuō)明決策變量j是單調(diào)的，此時(shí)問(wèn)題就好解決了。我們可以維護(hù)一個(gè)特殊的隊(duì)列，這個(gè)隊(duì)列只能從隊(duì)尾插入，

7、但是可以從兩端刪除。這個(gè)隊(duì)列滿(mǎn)足以及。1．計(jì)算狀態(tài)前，若，表示，即決策沒(méi)有優(yōu)，應(yīng)當(dāng)刪除，直至。2．計(jì)算狀態(tài)時(shí)，有。3．計(jì)算狀態(tài)后向隊(duì)列插入新的決策。若，表示在比優(yōu)之前就將比優(yōu)，沒(méi)必要保存。因此刪除，直至。每個(gè)狀態(tài)計(jì)算的復(fù)雜度都為，維護(hù)隊(duì)列的總復(fù)雜度為，因此整個(gè)算法的時(shí)間復(fù)雜度為。問(wèn)題得到解決！本例直接利用決策的單調(diào)性，運(yùn)用這一特殊的隊(duì)列成功地將算法的復(fù)雜度降低，而有的動(dòng)態(tài)規(guī)劃問(wèn)題，雖然表面上看起來(lái)決策不單調(diào)，無(wú)法直接套用上面介紹的優(yōu)化方法，但是只要充分挖掘條件中隱含的單調(diào)關(guān)系，并對(duì)數(shù)據(jù)作出相應(yīng)的調(diào)整變形，仍然可以利用類(lèi)似的方法實(shí)現(xiàn)時(shí)間上的“降

8、維”?！締?wèn)題二】貨幣兌換（BOI2003）你每天會(huì)收到一些貨幣A112006年全國(guó)信息學(xué)冬令營(yíng)講座，可能正也可能負(fù)，銀行允許你在某天將手頭所有的貨幣A兌換成B。第i