論文-從一類單調(diào)性問(wèn)題看算法的優(yōu)化

PAGEPAGE1從一類單調(diào)性問(wèn)題看算法的優(yōu)化【關(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ì)一類單調(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ì)列在一類單調(diào)性問(wèn)題中的運(yùn)用，來(lái)討論這種思想的具體應(yīng)用。隊(duì)列是一種我們非常熟悉的數(shù)據(jù)結(jié)構(gòu)。最常見(jiàn)的隊(duì)列是一種先進(jì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）從山頂上到山底下沿著一條直線種植了n棵老樹(shù)。當(dāng)?shù)氐恼疀Q定把他們砍下來(lái)。為了不浪費(fèi)任何一棵木材，樹(shù)被砍倒后要運(yùn)送到鋸木廠。木材只能按照一個(gè)方向運(yùn)輸：朝山下運(yùn)。山腳下有一個(gè)鋸木廠。另外兩個(gè)鋸木廠將新修建在山路上。你必須決定在哪里修建兩個(gè)鋸木廠，使得傳輸?shù)馁M(fèi)用總和最小。假定運(yù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行，每行有兩個(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ù)到山腳的鋸木廠的距離。保證所有樹(shù)運(yùn)到山腳的鋸木廠所需要的費(fèi)用小于2000000000分。輸出輸出只有一行一個(gè)數(shù)：最小的運(yùn)輸費(fèi)用。樣例輸入9122133113216211211輸出26在解決這一問(wèn)題時(shí)，首先我們要明確，將鋸木廠建立在相鄰兩棵樹(shù)之間是沒(méi)有任何意義的，否則我們可以將這樣的鋸木廠上移到最近的一棵樹(shù)處，此時(shí)運(yùn)送上方樹(shù)木的費(fèi)用減少，運(yùn)送下方樹(shù)木的費(fèi)用沒(méi)有變化，總費(fèi)用降低。為了方便討論，我們先作如下定義：假設(shè)山腳鋸木場(chǎng)處也有一棵樹(shù)，編號(hào)為，并且。表示第1棵樹(shù)到第棵樹(shù)的質(zhì)量和，即。表示第1棵樹(shù)到第棵樹(shù)的距離，即。特別的，有，表示第1棵樹(shù)到自己的距離為0。表示在第棵樹(shù)處建一個(gè)鋸木廠，并且將第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)用，則有。直接用這個(gè)式子計(jì)算的時(shí)間復(fù)雜度為，由于問(wèn)題規(guī)模太大，直接使用這一算法必然超時(shí)，因此我們必須對(duì)算法進(jìn)行優(yōu)化。在討論如何進(jìn)行優(yōu)化以前，我們首先證明下面這一猜想。[猜想]如果在位置建設(shè)第二個(gè)鋸木廠,第一個(gè)鋸木廠的位置是時(shí)最優(yōu)。那么如果在位置建設(shè)第二個(gè)鋸木廠,第一個(gè)鋸木廠的最佳位置不會(huì)小于。證明：令表示決策變量取時(shí)的值，即。設(shè)，則有若，則有將含K的項(xiàng)移到不等式左邊，整理得我們令，當(dāng)時(shí)因?yàn)?，所以?duì)于有。證畢。由上面的證明，可以說(shuō)明決策變量j是單調(diào)的，此時(shí)問(wèn)題就好解決了。我們可以維護(hù)一個(gè)特殊的隊(duì)列，這個(gè)隊(duì)列只能從隊(duì)尾插入，但是可以從兩端刪除。這個(gè)隊(duì)列滿足以及。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)整變形，仍然可以利用類似的方法實(shí)現(xiàn)時(shí)間上的“降維”?！締?wèn)題二】貨幣兌換（BOI2003）你每天會(huì)收到一些貨幣A，可能正也可能負(fù)，銀行允許你在某天將手頭所有的貨幣A兌換成B。第i天的兌換比率是1A：iB，同時(shí)你必須再多付出tB被銀行收取。在N天你必須兌換所有持有的貨幣A任務(wù)找一個(gè)方案使第N天結(jié)束時(shí)能得到最多的貨幣B輸入文件第一行是整數(shù)N,T第二行是N個(gè)整數(shù)Ai，表示第i天開(kāi)始時(shí)得到Ai的A幣輸出文件將最終得到的最多的B貨幣數(shù)寫(xiě)到文件數(shù)據(jù)范圍1≤N≤345670≤T≤34567樣例輸入71-103-24–623樣例輸出17我們很容易得到問(wèn)題的基本解決方法：定義表示第一天到第天總共得到了多少A幣，特別的，有表示以第天作為一個(gè)分割點(diǎn)，并且將第天到第天得到的A幣進(jìn)行一次性兌換可以得到的B幣數(shù)。則，特別的，當(dāng)時(shí)，有。求出所有的時(shí)間復(fù)雜度為，此后求任意的時(shí)間復(fù)雜度都為。設(shè)表示以第天作為一個(gè)分割點(diǎn)，最多可以得到多少個(gè)B幣。則。直接用這個(gè)式子計(jì)算的時(shí)間復(fù)雜度為，不能滿足要求。由于本題中可正可負(fù)，使得不滿足單調(diào)性，只要推倒一下就會(huì)發(fā)現(xiàn)，我們不能像上一題一樣證明出決策的單調(diào)性。因此我們好像無(wú)法采用上例中相同的方法來(lái)實(shí)現(xiàn)“降一維”。但我們很自然地聯(lián)想到，如果可以通過(guò)一定的變換，將的值變?yōu)槿糠秦?fù)或者非正，問(wèn)題就迎刃而解了。注意到這樣一個(gè)條件：第i天的兌換比率是1A：iB，也就是說(shuō)，時(shí)間越往后，A幣越值錢。也就是說(shuō)，A幣兌換B幣的利用這一重要條件作為突破口，考慮一種貪心的思想：如果當(dāng)前手上的A幣數(shù)為正，那么我們可以不忙著將其換成B幣，因?yàn)榱舻揭院笤贀Q，不但可以減少T的消耗，還可以使得兌換的比例更高?；谶@種思想，我們很自然地得到了如下猜想。[猜想]若{ai}序列中有一段連續(xù)的子序列，滿足：，，,……，均為非負(fù)數(shù)，而為負(fù)數(shù)，則當(dāng)在第i天收到了的貨幣A后，一定存在某個(gè)最優(yōu)方案，使得我們不急于在第天兌換，而是繼續(xù)在第天收到的A幣，第天收到的A幣，直到第天收到的A幣，再看情況決定是否兌換。這個(gè)猜想可以用反證法得到證明，下面給出證明。證明:假設(shè)某個(gè)最優(yōu)方案在區(qū)間中，存在一個(gè)或多個(gè)兌換點(diǎn)，設(shè)最早的一個(gè)兌換點(diǎn)在第天。那么設(shè)從上次兌換點(diǎn)到第天為止，共余下了的A幣，則：情況一：為非負(fù)數(shù)：那么顯然到第天的兌換點(diǎn)我們余下的錢將不會(huì)小于，取消這個(gè)兌換點(diǎn)，將其并入后一個(gè)兌換點(diǎn)一起兌換，既提高了手中A幣的價(jià)值，又省去了一次兌換手續(xù)費(fèi)T。情況二：為負(fù)數(shù)：將這個(gè)兌換點(diǎn)提前至第天，提前脫手了負(fù)數(shù)的A幣，相應(yīng)地可以使付出的B幣減少，而且將區(qū)間內(nèi)的非負(fù)數(shù)歸入下一個(gè)兌換點(diǎn)，得到的收益不會(huì)比原來(lái)少。綜上兩種情況，無(wú)論如何我們都可以通過(guò)調(diào)整將第天的兌換點(diǎn)去掉，收入?yún)s沒(méi)有減少或者更高，因此假設(shè)不成立，前面的猜想得到了證明。這個(gè)猜想告訴我們，如果非負(fù)，我們不用急著兌換，而是等到第2天，看，如果還是非負(fù)，繼續(xù)考慮第3天，第4天……，直到出現(xiàn)最小的，滿足（如果找不到這樣的，則令）。顯然一定存在某個(gè)最優(yōu)方案，使得第1到第天均不是兌換點(diǎn)。因此，我們可以將序列壓縮成一個(gè)數(shù)。類似地，我們繼續(xù)從第天考慮起，找到一個(gè)最小的，滿足（如果不存在，則令）。同樣的道理，第到第天均不是兌換點(diǎn)，我們可以繼續(xù)將壓縮成一個(gè)數(shù)。依次類推，用同樣的方法，可以將整個(gè)序列壓縮，變成一個(gè)長(zhǎng)度為的序列。序列有個(gè)很重要的特征：除了最后一個(gè)元素可能非負(fù)外，其它所有元素為負(fù)數(shù)。因此，相應(yīng)的除了最后一個(gè)元素外，一定滿足單調(diào)性。只要我們對(duì)最后一個(gè)元素做特殊處理，就可以完全套用前面的那個(gè)問(wèn)題的方法來(lái)解決了。至此，我們成功地將原算法的時(shí)間復(fù)雜度降了一維！在非動(dòng)態(tài)規(guī)劃問(wèn)題中的應(yīng)用對(duì)于一些非動(dòng)態(tài)規(guī)劃的問(wèn)題，如果能夠發(fā)現(xiàn)題中隱含的單調(diào)關(guān)系，同樣可以運(yùn)用一個(gè)類似的隊(duì)列來(lái)實(shí)現(xiàn)時(shí)間上的“降維”?！締?wèn)題三】旅行問(wèn)題（POI2004）John打算駕駛一輛汽車周游一個(gè)環(huán)形公路。公路上總共有車站，每站都有若干升汽油（有的站可能油量為零），每升油可以讓汽車行駛一千米。John必須從某個(gè)車站出發(fā)，一直按順時(shí)針（或逆時(shí)針）方向走遍所有的車站，并回到起點(diǎn)。在一開(kāi)始的時(shí)候，汽車內(nèi)油量為零，John每到一個(gè)車站就把該站所有的油都帶上（起點(diǎn)站亦是如此），行駛過(guò)程中不能出現(xiàn)沒(méi)有油的情況。任務(wù)：判斷以每個(gè)車站為起點(diǎn)能否按條件成功周游一周。輸入：第一行是一個(gè)整數(shù)，表示環(huán)形公路上的車站數(shù)。接下來(lái)行，每行兩個(gè)整數(shù)。第行含有：，表示第號(hào)車站的存油量；，表示第號(hào)車站到下一站的距離。輸出：輸出共行，如果從第號(hào)車站出發(fā)，一直按順時(shí)針（或逆時(shí)針）方向行駛，能夠成功周游一圈，則在第行輸出TAK，否則輸出NIE。樣例輸入53112520154樣例輸出TAKNIETAKNIETAK我們探討一下本題的解決方法。算法一：最容易想到的方法是枚舉所有車站作為起點(diǎn)，并且模擬汽車的行駛過(guò)程，看能否周游一圈，該方法的時(shí)間復(fù)雜度為，就本題的規(guī)模而言，完全無(wú)法承受，優(yōu)化勢(shì)在必行！算法二：簡(jiǎn)單的枚舉法之所以低效，最根本的原因就在于，我們?cè)谝来闻袛喔鱾€(gè)車站作為起點(diǎn)能否可行的時(shí)候，沒(méi)有充分利用前面得到的某些結(jié)果。由于順時(shí)針和逆時(shí)針行走，在本質(zhì)上是一樣的，因此我們暫且只考慮順時(shí)針行走的情況。原題中帶有兩個(gè)參量和，為了減少思考的復(fù)雜度，不妨將其壓縮成一個(gè)。令，從第站走到下一站，車內(nèi)的汽油增加（或減少）了多少。此外，為了方便討論，我們將環(huán)拆開(kāi)來(lái)，得到一個(gè)長(zhǎng)度為的鏈并滿足：設(shè)表示序列中前項(xiàng)的總和，即，特別的，有此時(shí)，我們可以清楚地看到，要判斷從某個(gè)車站出發(fā)，能否成功地周游一圈，實(shí)際上就是看，，……這個(gè)數(shù)中是否存在負(fù)數(shù)，如果有負(fù)數(shù)，則表示中途一定會(huì)出現(xiàn)沒(méi)有油的情況，否則可以順利行駛一周。如果我們還是像最樸素的方法一樣，通過(guò)循環(huán)來(lái)查找這個(gè)數(shù)中是否存在負(fù)數(shù)，算法復(fù)雜度沒(méi)有得到任何優(yōu)化。但是我們注意到，如果個(gè)數(shù)中的最小數(shù)非負(fù)，那么這個(gè)數(shù)全部非負(fù)。求個(gè)數(shù)中的最小數(shù)，很自然的讓我們聯(lián)想到了用堆來(lái)處理。用一個(gè)大小為的堆保存，……，判斷，，……中是否存在負(fù)數(shù)，實(shí)際上就是判斷當(dāng)前堆中的最小數(shù)是否小于，可以用的復(fù)雜度實(shí)現(xiàn)。在枚舉起始站的時(shí)候，隨著的增加，我們相應(yīng)地要將從堆中刪除，并將插入堆中，刪除插入的時(shí)間復(fù)雜度均為，因此整個(gè)算法的時(shí)間復(fù)雜度為。這樣，我們通過(guò)充分利用已經(jīng)得到的結(jié)果，得到了一個(gè)比剛剛好得多的算法。但是本題的數(shù)據(jù)范圍極大，的時(shí)間復(fù)雜度仍然不是特別理想，我們期望構(gòu)造出更好的算法。算法三：受到算法二的啟發(fā)，我們注意到，本題還可以是這樣理解：給定一個(gè)數(shù)列，以及個(gè)區(qū)間，每個(gè)區(qū)間滿足。要求你對(duì)于每個(gè)區(qū)間，給出中最小值的編號(hào)（如果存在多個(gè)這樣的編號(hào)，任意輸出一個(gè)即可）。很明顯，這個(gè)問(wèn)題可以套用標(biāo)準(zhǔn)的的RMQ算法得到解決。這樣算法的時(shí)間復(fù)雜度就成功的降為了。問(wèn)題到此似乎得到了完美解決，但是標(biāo)準(zhǔn)RMQ算法的編程復(fù)雜度很高，我們很自然地會(huì)期望得到一個(gè)更容易實(shí)現(xiàn)的高效算法。注意一下這個(gè)區(qū)間，發(fā)現(xiàn)它們的左右端點(diǎn)都是嚴(yán)格遞增的！因此本題和一般的RMQ問(wèn)題又存在著些許不同之處，或許利用區(qū)間的的單調(diào)性，可以像問(wèn)題二一樣得到一個(gè)高效且容易實(shí)現(xiàn)的算法。算法四：受到算法三的啟發(fā)，我們嘗試像例一一樣，猜想個(gè)最小值編號(hào)是滿足單調(diào)性的。其實(shí)只要再回過(guò)頭去分析一下算法二的執(zhí)行過(guò)程，注意到，如果某一次刪去的和插入的都很大，對(duì)堆中的最小數(shù)是不夠成影響的。順著這個(gè)思路往下想，我們很驚喜地發(fā)現(xiàn)如下規(guī)律：如果在某一段中，存在，使得，那么在以后的枚舉中無(wú)論如何都不可能成為堆中最小的元素（因?yàn)榭隙ㄒ认葎h除出堆，而又比大），直到它被刪除出堆。這樣剛剛的猜想得到了證明！其實(shí)真是因?yàn)楸４孢^(guò)多對(duì)求解無(wú)意義的數(shù)據(jù)，直接導(dǎo)致了算法二的低效。至此，我們發(fā)現(xiàn)此時(shí)的問(wèn)題和問(wèn)題一、二有著很大的相似性，因此我們完全可以采用類似的方法解決：1．維護(hù)一個(gè)特殊的隊(duì)列，表示有可能在今后的枚舉中成為某一段的最小值。這個(gè)隊(duì)列只能從隊(duì)尾插入，但可以從兩端刪除，并且要滿足。2．判斷以作為起點(diǎn)站前，若，直接將從隊(duì)列中刪除，接下來(lái)判斷，若，則表示在今后不可能成為某一段的最小值，是多余的，將其從隊(duì)列中刪除，直到隊(duì)列為空或，最后將插入隊(duì)列。3．若，則表示以作為起點(diǎn)的這一段中不會(huì)出現(xiàn)負(fù)數(shù)，標(biāo)記從出發(fā)，可以成功行駛一周。判斷每個(gè)作為出發(fā)點(diǎn)可行的時(shí)間復(fù)雜度為，維護(hù)隊(duì)列的時(shí)間復(fù)雜度為，因此整個(gè)算法的時(shí)間復(fù)雜度為。這個(gè)算法的時(shí)空效率在理論上和算法三差不多，不過(guò)實(shí)現(xiàn)難度要比算法三簡(jiǎn)單得多，甚至比用堆優(yōu)化的算法二還要容易！至此，本題得到了完美的解決！下面是對(duì)四個(gè)算法的比較：

空間復(fù)雜度時(shí)間復(fù)雜度實(shí)現(xiàn)難度算法一O(N)O(N^2)很容易算法二O(N)O(Nlog2N)簡(jiǎn)單算法三O(N)O(N)難算法四O(N)O(N)簡(jiǎn)單三、總結(jié)：本文的三個(gè)例子，都是通過(guò)充分挖掘問(wèn)題當(dāng)中隱含的單調(diào)關(guān)系，運(yùn)用特殊的隊(duì)列，成功地實(shí)現(xiàn)