一類單調(diào)問題的求解中山紀(jì)念中學(xué) 宋新波1一類課資一類課資例0.老徐真人秀做到的？請(qǐng)老徐回答當(dāng)時(shí)是怎么通過(guò)程序來(lái)快速選擇。老徐是編程達(dá)人，決定天的最美味的蘋果。只會(huì)吃天數(shù)不超過(guò)老徐有個(gè)怪癖，每一天干，供同一種美味的蘋果若天，每一天節(jié)目組都提個(gè)真人秀，節(jié)目共錄制最美杭城人老徐參加一1061NMMN隨手扔過(guò)來(lái)下面這個(gè)：直接告訴你答案，當(dāng)時(shí)老徐是大師，當(dāng)然不會(huì)，老徐的做法如下：別為天提供的蘋果美味度分，比如，79,73,78,75,80545MNday180day275day378day473day57980807875，既新鮮又美味，既新鮮又美味808079737978day5-day1=4天天792一類課資一類課資一.單調(diào)隊(duì)列及應(yīng)用 。隊(duì)列中的最大值在隊(duì)首中維護(hù)單調(diào)減的隊(duì)列，如例中是單調(diào)減的。素是單調(diào)的，如例由得隊(duì)列中保留的元直接刪除。沒有存在的必要，可以比“既新鮮又美味”，跟，且，如果滿足與中，區(qū)間中兩個(gè)元素如例右移向右平移的。遞增。查詢區(qū)間是隨著時(shí)，非遞減，當(dāng)左邊界遞增，的增加，右邊界。隨著，右邊界中，區(qū)間左邊界如例，天選擇的蘋果的美味度表示老徐第天發(fā)放蘋果的美味度，表示第中，設(shè)如例0 0最最優(yōu)優(yōu)選選擇擇在在隊(duì)隊(duì)首首：保保持持隊(duì)隊(duì)列列單單調(diào)調(diào)：去去除除冗冗余余狀狀態(tài)態(tài)：區(qū)區(qū)間間出出現(xiàn)現(xiàn)平平移移：維維護(hù)護(hù)區(qū)區(qū)間間最最值值：五五大大要要點(diǎn)點(diǎn)：001, 1max01, 1maxmax0aaaaaaallrrlaajjkjkkjiiiiijijkiMiiiMiijMiifiifi3一類課資一類課資一.單調(diào)隊(duì)列及應(yīng)用 結(jié)構(gòu)。優(yōu)于堆或線段樹等數(shù)據(jù)時(shí)間復(fù)雜度為進(jìn)出隊(duì)列各一次，所以由于每個(gè)元素最多只會(huì)最優(yōu)答案在隊(duì)首插入元素刪除隊(duì)首元素刪除隊(duì)尾元素中的代碼如下：例,;: ;: );();();()(1:; 0:; 1:0NOendstqaifiienqenincstincthenMstqiifendecdoenqaiaandstenwhilebegindontoiforenst代碼實(shí)現(xiàn)：代碼實(shí)現(xiàn)：4一類課資一類課資例1.NOIP2010初賽烽火傳遞。，的數(shù)據(jù)，對(duì)于的數(shù)據(jù)，對(duì)于一行，表示答案。代價(jià)。個(gè)烽火臺(tái)發(fā)出信號(hào)所需，表示第行，每行一個(gè)數(shù)接下來(lái)個(gè)發(fā)出信號(hào)。個(gè)烽火臺(tái)中至少要有一表示在連續(xù)表示烽火臺(tái)的個(gè)數(shù)，。其中第一行：兩個(gè)整數(shù)。座城市之間準(zhǔn)確出傳遞襲之時(shí)，情報(bào)能在這兩少代價(jià)，才能使敵軍來(lái)請(qǐng)計(jì)算總共最少花費(fèi)多個(gè)發(fā)出信號(hào)。個(gè)烽火臺(tái)中至少要有一連續(xù)使情報(bào)準(zhǔn)確地傳遞，在號(hào)都有一定代價(jià)。為了發(fā)出信個(gè)烽火臺(tái)，每個(gè)烽火臺(tái)之間有遞軍情，在某兩座城市晚燃燒干柴，以火光傳通過(guò)濃煙表達(dá)信息；夜白天燃燒柴草，上。一旦有敵情發(fā)生，般建在險(xiǎn)要或交通要道要的軍事防御設(shè)施，一烽火臺(tái)又稱烽燧，是重100000100%100;1000%5026521435,WWiiNMNMiNMMNMNMN數(shù)據(jù)范圍：數(shù)據(jù)范圍：樣例輸出：樣例輸出：樣例輸入：樣例輸入：輸出格式：輸出格式：輸入格式：輸入格式：題目描述：題目描述：5一類課資一類課資例1.NOIP2010初賽烽火傳遞 。間復(fù)雜度為使用單調(diào)隊(duì)列優(yōu)化，時(shí)在隊(duì)首。持單調(diào)遞增，最優(yōu)決策，所以隊(duì)列中的元素保刪除，可以且，如果而且區(qū)間是向右平移的時(shí)要計(jì)算區(qū)間最小值，上式計(jì)算答案時(shí)時(shí)程：”得到以下狀態(tài)轉(zhuǎn)移方臺(tái)的位置通過(guò)考慮“前一個(gè)烽火”所需最小代價(jià)。個(gè)烽火臺(tái)一定發(fā)出信號(hào)個(gè)烽火臺(tái)傳遞情報(bào)且第表示“在前動(dòng)態(tài)規(guī)劃：狀態(tài)NOjfjkjfkfifNiMNifAnsMiijMijfMiifjiiifwwii1 ,1maxmin1min分析：分析：6一類課資一類課資例2.GDKOI2009猴子。，：吃到的香蕉數(shù)。個(gè)整數(shù)，為猴子最多能輸出只有一行，包含一?？偸俏恢谩２⑶覜]有兩棵樹在同一從近到遠(yuǎn)排列。輸入保證這些樹按照樹到猴子所在樹的距離上的香蕉數(shù)，以及這棵，分別表示每棵香蕉樹個(gè)整數(shù)行每行包含兩。下面最多跳躍次數(shù)距離，猴子每次跳躍的最大，分別是香蕉樹的棵數(shù)輸入第一行為三個(gè)整數(shù)多能吃多少個(gè)香蕉呢？香蕉都吃了。那么它最，它就會(huì)把那棵樹上的。每當(dāng)他跳到一棵樹上得太遠(yuǎn)或跳的次數(shù)太多跳力也有限，它不能一次棵樹上。同時(shí)猴子的體只想從一棵樹跳到另一它又不想在地上走，而想吃盡量多的香蕉，但棵樹上。這個(gè)猴子當(dāng)然則在這排香蕉樹的第一在同一直線上，而猴子蕉樹，這些香蕉樹都種一個(gè)猴子找到了很多香10000,5000%100;2000%50;100%3010976543806202550,0DNMNMNMNMDNbabbaiiii數(shù)數(shù)據(jù)據(jù)范范圍圍：樣樣例例輸輸出出：樣樣例例輸輸入入：輸輸出出格格式式：輸輸入入格格式式：題題目目描描述述：7一類課資一類課資例2.GDKOI2009猴子。時(shí)間復(fù)雜度為最優(yōu)值在隊(duì)首。調(diào)遞減的隊(duì)列。移的，可以維護(hù)一個(gè)單的增加，區(qū)間是向下平值，同一列隨著大列的連續(xù)元素的區(qū)間最時(shí)需要計(jì)算第，計(jì)算按照列從小到大來(lái)處理答案時(shí)且其中時(shí)：得到以下狀態(tài)轉(zhuǎn)移方程點(diǎn)考慮最后一次跳躍的起?？脴渥疃嗄艹远嗌傧憬洞翁S跳到第棵樹不超過(guò)表示從第動(dòng)態(tài)規(guī)劃：狀態(tài)NMOijjifMNfAnsjDikjkfijifkijjifbbaakii1, 11101,max0,1,0分析：分析：ij-1j8一類課資一類課資例3.多重背包且價(jià)值總和最大。不超過(guò)背包容量，使這些物品的體積總和。選擇物品裝入背包可價(jià)值是，件可用，體積是種物品最多有的背包。第種物品和一個(gè)容量為有wvmiiiiVN9一類課資一類課資例3.多重背包：分別用藍(lán)色和紅色標(biāo)記要用到的元素示意圖，和觀察計(jì)算這里不做介紹當(dāng)然用倍增法優(yōu)化到時(shí)間復(fù)雜度為下狀態(tài)轉(zhuǎn)移方程：個(gè)物品裝幾個(gè)”得到以通過(guò)考慮“第值。個(gè)物品能獲得的最大價(jià)的背包來(lái)裝前表示用容量為背包問題，定義狀態(tài)vmvmwviNiNiiiiiijifjifmVOVOjxxxjifijifiijjifi,*,*,min0*, 100,121log分析：分析：iji-1j-vij+vi10一類課資一類課資例3.多重背包NVOjjikkkjifkkkjifkkkjifjifkjifjifjifjifjifjifjifvvvxxxwxvxvwxvxvxxxvxvxwxvxwxvxxxxxvviiiiiiiiiiiiiiiii時(shí)間復(fù)雜度為空間。的值分批次處理以節(jié)省按照模當(dāng)然也可以把的狀態(tài)等于模對(duì)應(yīng)背包容量個(gè)單調(diào)隊(duì)列，其中隊(duì)列建立一行來(lái)做，每一行需要從小到大來(lái)處理，一行按可以永久刪除。優(yōu)，還是比的，跟上面的不等式是等價(jià)，而不等式對(duì)應(yīng)著同樣的可選決策對(duì)應(yīng)著的可選決策來(lái)說(shuō)于后面的某一個(gè)狀態(tài)可以直接刪除。因?yàn)閷?duì)時(shí)，且滿足：如果時(shí)，對(duì)于兩個(gè)可選決策計(jì)算在向右平移；區(qū)間相對(duì)時(shí)涉及到的元素組成的計(jì)算等距的元素，距離為時(shí)涉及的元素是上一行置連續(xù)的元素，如計(jì)算注意這里的區(qū)間不是位：活運(yùn)用單調(diào)隊(duì)列來(lái)優(yōu)化由上圖發(fā)現(xiàn)該題可以靈,00*, 1*, 1,*,*,*, 1*, 1,11211222211111221221程序?qū)崿F(xiàn)：程序?qū)崿F(xiàn)：去除冗余保持單調(diào)：去除冗余保持單調(diào)：區(qū)間出現(xiàn)平移：區(qū)間出現(xiàn)平移：維護(hù)區(qū)間最值：維護(hù)區(qū)間最值：分析：分析：11一類課資一類課資例4.HNOI2008Toy1072,1 ,50000141243145118ccLxcciijikkiLNNLNLPLxPijxjiPODZiNNPODZODZPP數(shù)據(jù)范圍：數(shù)據(jù)范圍：樣例輸出：樣例輸出：樣例輸入：樣例輸入：輸出格式：輸出格式：輸入格式：輸入格式：題目描述：題目描述：輸出最小費(fèi)用。行輸入，接下來(lái)和第一行輸入兩個(gè)整數(shù)，但他希望費(fèi)用最小。甚至超過(guò)意長(zhǎng)度的容器，他可以制造出任教授不關(guān)心容器的數(shù)目是一個(gè)常量。，其中，其制作費(fèi)用為度為授的研究，如果容器長(zhǎng)教器長(zhǎng)度有關(guān)，根據(jù)。制作容器的費(fèi)用與容，那容器的長(zhǎng)度將為件玩具放在一個(gè)容器中到第如果將第形式地說(shuō)，個(gè)單位長(zhǎng)度的填充物。玩具之間要加入個(gè)玩具，那么相鄰兩件果一個(gè)一維容器中有多號(hào)是連續(xù)的。同時(shí)，如器中的玩具編教授要求在一個(gè)一維容。為了方便整理，處理后一維長(zhǎng)度是件玩具經(jīng)過(guò)件玩具，第的到號(hào)為教授有編一維容器中。維，再裝到一種特殊的可以將任意物品變成一來(lái)給玩具裝箱。自己的物體維度壓縮器教授使用北京去。決定把所有玩具都運(yùn)到堆智力玩具。于是，他他割舍不下自己的一大教授要去看奧運(yùn)，但是月12一類課資一類課資例4.HNOI2008Toy ，超時(shí)。直接做時(shí)間復(fù)雜度為入的分析。的單調(diào)性，需要深就可以刪除”這樣明顯沒有前面幾個(gè)例子中“卻沒有分離，的，這兩個(gè)參數(shù)是完全分離和這三項(xiàng)中式子中則有對(duì)應(yīng)的費(fèi)用記為?？蛇x決策定義離注意展開過(guò)程中參數(shù)分，是未知的，展開平方式的含有這些量相當(dāng)于已知，而時(shí)，計(jì)算其中下狀態(tài)轉(zhuǎn)移方程：這段連續(xù)的玩具，得以到設(shè)是裝在同一個(gè)容器中，假考慮哪些玩具與玩具的前綴和。為用，個(gè)玩具裝箱所需最小費(fèi)表示把前動(dòng)態(tài)規(guī)劃：狀態(tài)njififjjigjxigjxjxigififLjsisjicOjjjxigjijfjxigjfjfjjsjjxLisiigjsjjfjLisiifijjfifijiisiifjji2112222222,*2,1*211,1,1,1,1,1min121分析：分析：13一類課資一類課資例4.HNOI2008Toy 斜率優(yōu)化！題要用到新知識(shí)：兩個(gè)點(diǎn)形成的斜率，這，上面式子左邊像：是單調(diào)遞增的，所以有因再令jjjjjjixjjjxjjxjigjjxjigjjxjigxxyyisiixifiyxxigffxigfxigf211212212212221212222*2)()()()(1,1*211-21*211*221的前提條件：的前提條件：j jj j時(shí)時(shí)研究研究i if fi if fj jj j1 12 21 12 214一類課資一類課資例4.HNOI2008Toy 的結(jié)論：增的。下面有兩個(gè)重要都是單調(diào)的，都是單調(diào)和該題則必須滿足優(yōu)，令比，如果時(shí)，可選決策計(jì)算igixigTxxyyTifjjjjjjjjjjjj*2,)()()()(,211212211212斜斜率率優(yōu)優(yōu)化化： 再繼續(xù)維護(hù)！列基礎(chǔ)上加入新的決策時(shí)可以在之前維護(hù)的隊(duì)并且在是最優(yōu)的！優(yōu)。所以隊(duì)首比優(yōu)，比優(yōu)，比來(lái)說(shuō)，則對(duì)于所以可以刪除。優(yōu)，永遠(yuǎn)比時(shí)，有：，計(jì)算后面的是單調(diào)增的，則對(duì)于由于之間的斜率策如果隊(duì)列中相鄰兩個(gè)決。，, 11.,*2,.,*2,*2,*2*2,*2,*2,.,*2,*2,*2,.,11322113221111111322121iififigTigTigTxxygigyxTfiigigyxTyxigTigTigTigifjjjjjjjjjjjjjiiiijjjjjjjjjjkkkkkkk證證明明：最最優(yōu)優(yōu)決決策策是是隊(duì)隊(duì)首首元元素素即即：的的斜斜率率都都要要大大于于使使得得這這些些相相鄰鄰決決策策之之間間決決策策依依次次存存儲(chǔ)儲(chǔ)有有價(jià)價(jià)值值的的可可選選大大策策，使使得得隊(duì)隊(duì)列列中中從從小小到到可可以以刪刪除除其其中中的的冗冗余余決決 到到i i, ,時(shí)時(shí)，所所有有可可選選決決策策是是1 1結(jié)結(jié)論論1 1：計(jì)計(jì)算算15一類課資一類課資例4.HNOI2008Toyj1j2j3 可以刪除。得證！不可能成為最優(yōu)決策，出現(xiàn)了矛盾！所以優(yōu)比優(yōu)比。的過(guò)程中成為最優(yōu)決策有沒有可能在計(jì)算，分析即。鄰斜率單調(diào)遞減的情況，假設(shè)出現(xiàn)下圖所示相設(shè)隊(duì)列中三個(gè)相鄰決策jjjjjjjjjjjjjjjjjjjjjTigTigTigTfTT221323232211223221321,*2,*2,*2,證明：證明：決策之間的斜率單調(diào)增決策之間的斜率單調(diào)增結(jié)論2：可以維護(hù)相鄰結(jié)論2：可以維護(hù)相鄰 最最優(yōu)優(yōu)決決策策取取隊(duì)隊(duì)首首元元素素策策滿滿足足：應(yīng)應(yīng)該該維維護(hù)護(hù)隊(duì)隊(duì)列列中中相相鄰鄰決決綜綜上上：jjjjjjkkTTTig,.,*21322116一類課資一類課資例4.HNOI2008Toy ：最優(yōu)決策在隊(duì)首。；或者于直到隊(duì)列中元素個(gè)數(shù)小，循環(huán)做下去，則刪除隊(duì)首元素，如果取隊(duì)首兩個(gè)決策加入隊(duì)尾；：把新的可選決策或者列中的元素個(gè)數(shù)小于。循環(huán)做下去，直到隊(duì)則刪除隊(duì)尾元素如果策每次選隊(duì)列最后兩個(gè)決要插入新的可選決策取取頭頭刪刪頭頭：插插入入刪刪尾尾：igTigTiiTTiTTijjjjjjjjjjjjjjjjkkkkkkkkk*2,2*2,2,2112121111 步：下所以具體程序?qū)崿F(xiàn)分以遞增由于，坐標(biāo)是插入點(diǎn)，相當(dāng)于在二維平面中插入一個(gè)新的決策計(jì)算枚舉維護(hù)相鄰決策滿足：的整個(gè)過(guò)程中，始終要在計(jì)算4,.,*213221ixiyixiiifiTTTigfjjjjjjkk程序?qū)崿F(xiàn)：程序?qū)崿F(xiàn)：17一類課資一類課資例4.HNOI2008Toy動(dòng)畫演示：動(dòng)畫演示：j1j2j3j4j5T(j3,j4)T(j4,j5)T(j2,j3)T(j3,j5)T(j1,j2)2g(i)最優(yōu)決策為最優(yōu)決策為j218一類課資一類課資例4.HNOI2008Toy nOendistqtstqfifstincdoigstqstqtandenstwhileienqenincendecdoienqtenqenqtandenstwhilebegindontoiforenstf時(shí)間復(fù)雜度為取頭刪頭插入去尾;);,(cos 1: );()*2)1,() 1( ;: );();(),),1() 1(1:; 0:; 1:; 0: 0程序代碼：程序代碼：19一類課資一類課資例5.APIO2010特別行動(dòng)隊(duì)的戰(zhàn)斗力和更大。正后，沒有其他方案能使修。修正后的戰(zhàn)斗力和為為，修正后的戰(zhàn)斗力分別戰(zhàn)斗力分別為。特別行動(dòng)隊(duì)的初始，第三隊(duì)包含士兵，第二隊(duì)包含士兵和士兵含士兵特別行動(dòng)隊(duì)：第一隊(duì)包個(gè)士兵組成。此時(shí)，最佳方案是將。經(jīng)驗(yàn)公式中的參數(shù)為名士兵，和。例如你有最大。試求出這個(gè)最大動(dòng)隊(duì)修正后戰(zhàn)斗力之和編隊(duì)，使得所有特別行你要為這支部隊(duì)進(jìn)行。作為部隊(duì)統(tǒng)帥，現(xiàn)在是已知的系數(shù)其中式修正為將按如下經(jīng)驗(yàn)公的初始戰(zhàn)斗力總結(jié)出一支特別行動(dòng)隊(duì)。通過(guò)長(zhǎng)期的觀察，你之和，即為對(duì)內(nèi)士兵初始戰(zhàn)斗力戰(zhàn)斗力一支特別行動(dòng)隊(duì)的初始的士兵的初始戰(zhàn)斗力為編號(hào)為的序列。即為形如隊(duì)員的編號(hào)應(yīng)該連續(xù)，同一支特別行動(dòng)隊(duì)中戰(zhàn)場(chǎng)。出于默契的考慮若干特別行動(dòng)隊(duì)調(diào)入編號(hào)，要將他們拆分成到隊(duì)，士兵從名預(yù)備役士兵組成的部你有一支由94 , 1 , 44 , 3 , 44321320,10, 14, 3, 2, 24)0(,.,),.1,(1432121cbaacbacbxaxxxxikiiinnxxxxxxxxxkiiii題目描述：題目描述：1001 ,000,000,10, 15,000,000, 11:%100;000,10:%50;1000:%20 xicbannn數(shù)據(jù)范圍：數(shù)據(jù)范圍：20一類課資一類課資例5.APIO2010特別行動(dòng)隊(duì) 分?？梢缘弥苯幼觯瑫r(shí)間復(fù)雜度為其中。和這一項(xiàng)無(wú)法分離令盡量分離得：和未知。把已知，展開得其中則有：移，假設(shè)是的士兵”來(lái)進(jìn)行狀態(tài)轉(zhuǎn)個(gè)士兵在同一個(gè)行動(dòng)隊(duì)通過(guò)考慮“跟第的前綴和。為戰(zhàn)斗力修正戰(zhàn)斗力。別行動(dòng)隊(duì)能獲得的最大個(gè)士兵拆分成若干個(gè)特表示把前動(dòng)態(tài)規(guī)劃：狀態(tài)50,1,1*2max1*2*,1*1*1*21*11*1*2*1:1,1*1max,222222221111nisjsisjsjsisjsisxOijjsisaihjgifjijsisacisbaihjsbajfjgcisbajsisajsbajfjijicjsbisbajsisaajfijcjsisbajfifjiisiifi分析：分析：21一類課資一類課資例5.APIO2010特別行動(dòng)隊(duì) 上一題用斜率優(yōu)化！是單調(diào)的，可以考慮像的坐標(biāo)是的坐標(biāo)是中兩個(gè)點(diǎn)形成的斜率，其，上面式子左邊像上式得：是單調(diào)增的是正整數(shù)，因初始戰(zhàn)斗力：時(shí)isgsgsisassggisssisaggsisaihgsisaihgjjjjjjjjjjjjjjxxjjjjjjjjififjjijji22211121121211212112212,1,1*21111*21*21*212的前提條件的前提條件研究研究22一類課資一類課資例5.APIO2010特別行動(dòng)隊(duì) 個(gè)重要的結(jié)論：是單調(diào)增的，同樣有兩該題優(yōu)，必須滿足要比時(shí)換句話說(shuō)，優(yōu)，必須滿足比。如果，令時(shí)，可選決策根據(jù)上面分析：計(jì)算isisaTisaTssggTifjjjjjjjjjjjjjjjjjj*2,*2,11,212121211212122112應(yīng)用斜率優(yōu)化：應(yīng)用斜率優(yōu)化： 是最優(yōu)的！優(yōu)。所以隊(duì)尾元素比，優(yōu)，比優(yōu)，比所以可以刪除優(yōu)，永遠(yuǎn)比時(shí)，有：，計(jì)算對(duì)于后面的是單調(diào)增的，優(yōu)。由于比之間的斜率策如果隊(duì)列中相鄰兩個(gè)決。，jjjjjjjjjjjjjiiiijjjjjjjjjjkkkkkkkkkisaTisaTisaTyyxsaisayxTfiisyxisayxTyxisaTisaTisaTisaif1 -23121322111111322121.*2,.,*2,*2,*2*2,*2,*2,.,*2,*2,*2,.,證證明明：最最優(yōu)優(yōu)決決策策是是隊(duì)隊(duì)尾尾元元素素即即：大大于于相相鄰鄰決決策策之之間間的的斜斜率率都都依依次次存存儲(chǔ)儲(chǔ)可可選選決決策策，使使得得隊(duì)隊(duì)列列中中從從小小到到大大時(shí)時(shí)，可可以以刪刪除除冗冗余余決決策策結(jié)結(jié)論論1 1：計(jì)計(jì)算算23一類課資一類課資例5.APIO2010特別行動(dòng)隊(duì) 可以刪除。得證！不可能成為最優(yōu)決策，出現(xiàn)了矛盾！所以優(yōu)比優(yōu)比。的過(guò)程中成為最優(yōu)決策有沒有可能在計(jì)算，分析即。鄰斜率單調(diào)遞增的情況，假設(shè)出現(xiàn)下圖所示相設(shè)隊(duì)列中三個(gè)相鄰決策jjjjjjjjjjjjjjjjjjjjjTisaTisaTisaTfTT232213232211223221321,*2,*2,*2,證明：證明：決策之間的斜率單調(diào)減決策之間的斜率單調(diào)減結(jié)論2：可以維護(hù)相鄰結(jié)論2：可以維護(hù)相鄰 最最優(yōu)優(yōu)決決策策取取隊(duì)隊(duì)尾尾元元素素策策滿滿足足：應(yīng)應(yīng)該該維維護(hù)護(hù)隊(duì)隊(duì)列列中中相相鄰鄰決決綜綜上上：isaTTTjjjjjjkk*2,.,1322124一類課資一類課資例5.APIO2010特別行動(dòng)隊(duì) 。總時(shí)間復(fù)雜度為：最優(yōu)決策在隊(duì)尾。；或者個(gè)數(shù)小于下去，直到隊(duì)列中元素，循環(huán)做，則刪除隊(duì)尾元素，如果取隊(duì)尾兩個(gè)決策加入隊(duì)尾；：把新的可選決策或者列中的元素個(gè)數(shù)小于。循環(huán)做下去，直到隊(duì)則刪除隊(duì)尾元素如果策每次選隊(duì)列最后兩個(gè)決要插入新的可選決策nOisaTisaTiiTTiTTijjjjjjjjjjjjjjjjkkkkkkkkkkkkkkkk取取尾尾刪刪尾尾：插插入入刪刪尾尾：*2,2*2,2,111111 步：分以下遞增所以具體程序?qū)崿F(xiàn)由于，坐標(biāo)是插入點(diǎn)，相當(dāng)于在二維平面中插入一個(gè)新的決策計(jì)算枚舉維護(hù)相鄰決策滿足：的整個(gè)過(guò)程中，始終要在計(jì)算4,1,*2,.,13221ixigisiiifiisaTTTfjjjjjjkk程序?qū)崿F(xiàn)：程序?qū)崿F(xiàn)：25一類課資一類課資二.斜率優(yōu)化總結(jié) 都是單調(diào)的。和以上斜率不等式中是后加入的決策點(diǎn)設(shè)為了便于分析，我們假或如的不等式：到關(guān)于斜率的優(yōu)劣，使參數(shù)分離得對(duì)比兩個(gè)可選決策狀態(tài)轉(zhuǎn)移方程能通過(guò)igixigxxyyigxxyyTjjjjjjjjjjjjjjj221121212122121,兩個(gè)使用前提：兩個(gè)使用前提：26一類課資一類課資二.斜率優(yōu)化總結(jié) 。，最優(yōu)決策取隊(duì)首元素滿足：維護(hù)隊(duì)列中的相鄰決策單調(diào)減：，最優(yōu)決策取隊(duì)尾元素滿足：維護(hù)隊(duì)列中的相鄰決策單調(diào)增：，最優(yōu)決策取隊(duì)尾元素滿足：維護(hù)隊(duì)列中的相鄰決策單調(diào)減：，最優(yōu)決策取隊(duì)首元素滿足：維護(hù)隊(duì)列中的相鄰決策單調(diào)增：，種情況：的單調(diào)性”分為以下四”和“還是經(jīng)總結(jié)，根據(jù)“jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjkkkkkkkkTTTigigigTigTTTigigTigTTTigigTTTTigigigTgigTigT,.,;,.,;,.,;,.,13221211322121132212113221212121,四種情況：四種情況：27一類課資一類課資三.斜率優(yōu)化 。是單調(diào)的，以上斜率不等式中或如式。到一個(gè)類似斜率的不等的優(yōu)劣，使參數(shù)分離得比兩個(gè)可選決策狀態(tài)轉(zhuǎn)移方程能通過(guò)對(duì)不是單調(diào)的i但gixigigxxyyTjjjjjjjj12122121,28一類課資一類課資例6.游戲 慶語(yǔ)其慶語(yǔ)其驗(yàn)學(xué)校驗(yàn)學(xué)校出題人：北師大附屬實(shí)出題人：北師大附屬實(shí)數(shù)據(jù)范圍：數(shù)據(jù)范圍：樣例輸出：樣例輸出：樣例輸入：樣例輸入：輸出格式：輸出格式：輸入格式：輸入格式：題目描述：題目描述：。的數(shù)據(jù)，對(duì)于的數(shù)據(jù)，對(duì)于最多能得到的分?jǐn)?shù)。一個(gè)整數(shù)，表示。個(gè)數(shù)表示其中第個(gè)整數(shù)。第二行有第一行一個(gè)整數(shù)分。想知道他最多能得多少，沒有分。有分?jǐn)?shù)。他現(xiàn)在在原點(diǎn)上的所有分?jǐn)?shù)，原點(diǎn)沒現(xiàn)給出上。，他最后必須停在點(diǎn)上的分?jǐn)?shù)，且要求是其中的分?jǐn)?shù)，他將得到頂?shù)巾?，同時(shí)如果他從游戲里他只能向正方向他在玩一個(gè)游戲，這個(gè)頂?shù)饺我庹c(diǎn)上?，F(xiàn)在頂?shù)礁h(yuǎn)的地方，他能的頭變多了，于是他能現(xiàn)在內(nèi)的數(shù)軸上的整點(diǎn)上。之隔在整點(diǎn)可以頂?shù)脚c自己相化到數(shù)軸上，即從一個(gè)點(diǎn)上。我們現(xiàn)在將之簡(jiǎn)一個(gè)整點(diǎn)頂?shù)搅硪粋€(gè)整的位移，也就是從頂出前水平有限，每次只能是會(huì)造成位移的。他之從小就愛亂頂，但是頂500 ,100000%100;1000%6050111503,1)(*,jannWYFiainnWYFnnijjjaijjajiWYFkkWYF29一類課資一類課資例6.游戲 jjjjjjjjjjjjjjjjjjjjjjjnkkkTTTiaxxfxxiaffTiaiiafiaiiafjiiajOijjiiajfifijiif,.,.,1,*600 ,*max1322121121221112212212要滿足：可選決策隊(duì)列中從小到大排列的。即：之間的斜率是單調(diào)減的法可以得出，相鄰決策采用前面兩題類似的方還是有的！策之間的斜率的單調(diào)性就不存在了，但相鄰決中的結(jié)論類似于斜率優(yōu)化不是單調(diào)的！是遞增的，但橫坐標(biāo)的坐標(biāo)是形式，決策不等式左邊也是斜率的優(yōu)？比，什么情況下策沒有分離，考慮兩個(gè)決和，有一項(xiàng)是分。，直接做時(shí)間復(fù)雜度為方程：的，得到以下狀態(tài)轉(zhuǎn)移頂?shù)娇紤]最后一次是從的最大得分。表示從原點(diǎn)頂若干次到動(dòng)態(tài)規(guī)劃：分分析析：30一類課資一類課資例6.游戲 nnOiaTiaTTTTiaiaTiaTTTiaTifjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjxxxxxxxkxxxkkxxxxxxxxxxxxxxxxxkln,.,.,.,.,.,11211211111211322111 -21時(shí)間復(fù)雜度為法就可以找出率是單調(diào)減的，用二分因?yàn)橄噜彌Q策之間的斜就是最優(yōu)決策，且滿足因此只要都要優(yōu)！比后面的優(yōu)比都要優(yōu)！比前面的優(yōu)比。則有：假設(shè)最優(yōu)決策是時(shí)隊(duì)列中可選決策有計(jì)算分分法法求求最最優(yōu)優(yōu)決決策策方方法法一一：二二31一類課資一類課資例6.游戲 nnOlrxlyrjjjjllryllrxkrljjjififififififyxyxjjln312111,131*2131, 1,是的區(qū)間，時(shí)間復(fù)雜度也每次排除否則回到則直接比較找出答案，如果否則則如計(jì)算，取一開始可以使用三分法：峰的模型，單峰求極值所有決策點(diǎn)形成一個(gè)單在二維平面中畫出點(diǎn)作為縱坐標(biāo)，對(duì)應(yīng)的得分作為橫坐標(biāo)，把決策把隊(duì)列中的可選決策：三三分分法法求求最最優(yōu)優(yōu)決決策策方方法法二二好點(diǎn)好點(diǎn)壞點(diǎn)壞點(diǎn)32一類課資一類課資例6.游戲的時(shí)間復(fù)雜度也是值計(jì)算一次決策點(diǎn)對(duì)應(yīng)的的區(qū)間，每次三分只需每次刪除即：右的決策點(diǎn)。在新的有效區(qū)間中是靠右邊的無(wú)效區(qū)間，是壞點(diǎn)，刪除如果左的決策點(diǎn)；在新的有效區(qū)間中是靠左邊的無(wú)效區(qū)間，是壞點(diǎn)，刪除如果并滿足以下兩個(gè)要求：的比例固定，與和靠右決策點(diǎn)選擇靠左決策點(diǎn)長(zhǎng)度為另一種三分法，總區(qū)間：nOllylxyxlyxlxylxxyyyxxlyxyxlln*25-3*215*25-3,黃黃金金分分割割三三分分法法求求最最優(yōu)優(yōu)決決策策方方法法三三Lxy33一類課資一類課資四.斜率優(yōu)化 或最左邊策點(diǎn)不一定插在最右邊不單調(diào)時(shí)，插入新的決。但以上斜率不等式中或如式。到一個(gè)類似斜率的不等的優(yōu)劣，使參數(shù)分離得比兩個(gè)可選決策狀態(tài)轉(zhuǎn)移方程能通過(guò)對(duì)ixigigxxyyTjjjjjjjj都不是單調(diào)的i和gix12122121,34一類課資一類課資例7.NOI2007貨幣兌換券。次賣出操作賣出所有金操作使用完所有錢；每賣方案滿足：每次買進(jìn)必然存在一種最優(yōu)的買，：位小數(shù)。答案保留得的最大的金錢數(shù)目。天的操作結(jié)束時(shí)能夠獲，表示第只有一個(gè)實(shí)數(shù)。、行三個(gè)實(shí)數(shù)行，第接下來(lái)時(shí)擁有的錢數(shù)。能預(yù)知的天數(shù)以及初始分別表示小、第一行兩個(gè)正整數(shù)元錢。天后最多能夠獲得多少元錢，那么，如果開始時(shí)擁有他還希望能夠計(jì)算出來(lái)。券的價(jià)值以及券和天內(nèi)的經(jīng)知道了未來(lái)運(yùn)作和行情測(cè)算，他已員工，通過(guò)較長(zhǎng)時(shí)間的時(shí)一個(gè)很有經(jīng)濟(jì)頭腦的小行多次操作。注意：同一天內(nèi)可以進(jìn)；天恰好為例在第券的比券和供給顧客的的金券，并且，滿足提兌換給用戶總價(jià)值為元人民幣，交易所將會(huì)買入金券：顧客支付為人民幣；券以當(dāng)時(shí)的價(jià)值兌換的券和的為：將作為賣出比例，其意義內(nèi)的實(shí)數(shù)個(gè)賣出金券：顧客提供一兩個(gè)方面：易法。比例交易法分為便的交易方式：比例交易所提供了一種非常方為了方便顧客，金券交。單位金券元和券的價(jià)值分別為券和天中第人民幣數(shù)目。我們記錄位金券當(dāng)天可以兌換的當(dāng)時(shí)的價(jià)值，即每一單動(dòng)，兩種金券都有自己每天隨著市場(chǎng)的起伏波數(shù)。券的數(shù)目可以是一個(gè)實(shí)有一個(gè)自己的賬戶。金每個(gè)持有金券的顧客都。券以前簡(jiǎn)稱紀(jì)念券和券以下簡(jiǎn)稱紀(jì)念券發(fā)行交易兩種金券：工作。該金券交易所只最近在一家金券交易所小提提示示：數(shù)數(shù)據(jù)據(jù)規(guī)規(guī)模模和和約約定定：輸輸出出格格式式：輸輸入入格格式式：題題目目描描述述：109,1000 ,100100 ,000100%100;1000%60;10%403,)%100, 0)/()()(MaxprofitNNNNMaxprofitKNYSNNSRateBANYKBAIPIPbBOPAOPOPaBAkBBAAYRateBARateBARateBAkkkkkkkkk35一類課資一類課資例7.NOI2007貨幣兌換錢？天后用戶最多擁有多少元錢，問初始時(shí)用戶擁有。兩種金券的比例為、值的金券，買入的用所有的錢買入等價(jià)賣出所有的金券；如下操作：每一天用戶進(jìn)行若干次、分別具有單位價(jià)值、天天內(nèi)，第接下來(lái)的兩種金券進(jìn)行交易。、金券交易所可以對(duì)NSBABAiNBARateBAiii,問問題題簡(jiǎn)簡(jiǎn)述述：么不賣要么全賣。操作也是完全的，即要類似的，可以證明賣出么不買要么全部買進(jìn)；也就是說(shuō)，買進(jìn)操作要能使獲利最大化時(shí)，取當(dāng)能使獲利最大化時(shí)，取當(dāng)，則最后總利潤(rùn)買進(jìn)時(shí)使用錢的比例為。利為一元錢不買金券最后獲券到最后會(huì)獲利為券和元，假定一元錢買進(jìn)的，假設(shè)有在進(jìn)行買進(jìn)操作的時(shí)候01*1*,xqpxqpxqpqSqxSpxSxqpBAS提示的證明：提示的證明：36一類課資一類課資例7.NOI2007貨幣兌換 分。，間復(fù)雜度為可以用搜索來(lái)解決，時(shí)全部賣出進(jìn)全部賣出后再全部買全部買進(jìn)不進(jìn)行活動(dòng)種：動(dòng)有以下出每一天可能進(jìn)行的活根據(jù)上面的提示，總結(jié)404nO4 4方方法法一一：搜搜索索37一類課資一類課資例7.NOI2007貨幣兌換 分。，直接做時(shí)間復(fù)雜度為時(shí)下狀態(tài)轉(zhuǎn)移方程：根據(jù)上面的分析，得以獲利”這個(gè)子問題。天的最大第天賣出，這就涉及到“再在第天的最大獲利全部買入第這樣實(shí)際上就是要求把沒有進(jìn)行任何操作。天到第天，即第一次買入操作發(fā)生在第全部賣出：假設(shè)最后；進(jìn)：這種操作沒有意義全部賣出后再全部買沒有意義；全部買進(jìn)：這種操作天的最大獲利；利等于第不進(jìn)行活動(dòng)：最大獲天可以進(jìn)行的活動(dòng)：考慮第天的最大獲利表示前狀態(tài)601*1max1,1111,2nBARateBARateOijjfifiSifjNjNjjiiSfiifjjjiij方方法法二二：動(dòng)動(dòng)態(tài)態(tài)規(guī)規(guī)劃劃38一類課資一類課資例7.NOI2007貨幣兌換 jjjjjjjjjRateRatejRatejjjABjjRatejRatejjjjjjjBARatejRatejBjARatejBjARatejjjjjBARateBARateBARateBARatekkkjiiiiiiiiiijjjjjjjiijTTTjgjgjjgjgggggjgjgTggjgggjgjggjggjgjgjgjfjgjijf,.,.,*,*,*,*11,*132212112121212211221121122122112121212，利用前面所學(xué)易知：序列標(biāo)從小到大排序得決策把所有決策點(diǎn)按照橫坐，縱坐標(biāo)是的橫坐標(biāo)是的形式，決策點(diǎn)以上不等式左邊是斜率時(shí)，得：時(shí)，得：沒有單調(diào)性：更優(yōu)？比什么情況下、分析兩個(gè)決策則上式設(shè)枚舉到因?yàn)橐獜倪@里以上方程主要慢在方方法法三三：斜斜率率優(yōu)優(yōu)化化39一類課資一類課資例7.NOI2007貨幣兌換分。，時(shí)間復(fù)雜度為介紹。中的二分法，這里不再可以采用例不單調(diào)，尋找最優(yōu)決策因?yàn)槎伎梢?。或可以用平衡樹?lái)維護(hù)，。右邊的維護(hù)類似?；蛘邼M足個(gè)決策點(diǎn)少于，重復(fù)執(zhí)行直到左邊的則刪除，如果的前一個(gè)決策點(diǎn)和決策點(diǎn)的前一個(gè)次找其中左邊的維護(hù)可以每要保證斜率是遞減的，的左邊和右邊，兩邊都并分別維護(hù)插入不用插入，否則進(jìn)行出現(xiàn)了斜率上升，如果右邊的決策左邊的決策找到的操作如下：插入一個(gè)新決策間的斜率單調(diào)遞減！然后再維護(hù)相鄰決策之中間，尾，有可能會(huì)插在隊(duì)列點(diǎn)時(shí)不可以直接插在隊(duì)不單調(diào)時(shí)，插入新決策100ln6,2,11211122112121nnOSplayTreapxTTxTTxxxxxTxTxxgABxxxxxxxxxxxxxxii方方法法三三：斜斜率率優(yōu)優(yōu)化化40一類課資一類課資例7.NOI2007貨幣兌換j1j2j3j4j5j6j7T(j2,j3)T(j3,j7)T(j7,j4)T(j4,j5)T(j7,j5)T(j5,j6)動(dòng)畫演示：動(dòng)畫演示：41一類課資一類課資例7.NOI2007貨幣兌換 yBxABARateyBARateRatexBARateBARatejijijjjjjjjjjjjjiijjjfjfjfif*,*max對(duì)應(yīng)的獲利，決策令方方法法四四：線線性性規(guī)規(guī)劃劃42一類課資一類課資例7.NOI2007貨幣兌換天的價(jià)值都是一樣的；直線上每一個(gè)點(diǎn)在第，恰好為獲利的軸的截距為直線在直線方程為：的直線，過(guò)這個(gè)點(diǎn)作一條斜率為在二維平面上對(duì)應(yīng)著點(diǎn)決策iyxyxyjBByBxAByBxABABAxyBAyxiijijiijijiiiiijjiijj1*,幾幾何何意意義義：43一類課資一類課資例7.NOI2007貨幣兌換 決策。離原點(diǎn)最遠(yuǎn)的就是最優(yōu)所有交點(diǎn)中的直線條斜率為的直線，再過(guò)原點(diǎn)作一為過(guò)每個(gè)決策點(diǎn)作斜率平面上的點(diǎn)；天購(gòu)買金券對(duì)應(yīng)到二維在第時(shí)的獲利”計(jì)算就是用“使用決策的直線，兩直線的交點(diǎn)過(guò)原點(diǎn)作一條斜率為,11RateBARateiiiiiifj幾幾何何意意義義：最優(yōu)決策最優(yōu)決策44一類課資一類課資例7.NOI2007貨幣兌換的優(yōu)劣情況：和決策分析決策連線的斜率為和點(diǎn)點(diǎn)假設(shè)增加而減少隨著得決策點(diǎn)的降序排序，維護(hù)序列使相同時(shí)按照升序，把所有決策按照kjkjTkjxyyxxxxkj,斜斜率率單單調(diào)調(diào)減減優(yōu)優(yōu)化化二二：維維護(hù)護(hù)相相鄰鄰決決策策優(yōu)優(yōu)化化一一：去去除除冗冗余余BAiikjT,jkRateixy 直線 決策j與k一樣優(yōu),kj,T1BAiijkRateixy 直線 決策k更優(yōu),kj,T2BAiijkRateixy 直線 決策j更優(yōu),kj,T3BAii45一類課資一類課資例7.NOI2007貨幣兌換策，可以刪除。得證！永遠(yuǎn)不可能成為最優(yōu)決決策產(chǎn)生矛盾。，與前面的假設(shè)優(yōu)比優(yōu)比根據(jù)上面的分析：優(yōu)決策將來(lái)有沒有可能成為最在這種情況下現(xiàn)在包括考慮決策，即如下圖所示。滿足假設(shè)三個(gè)相鄰的決策klkTkjTkjTlkTlkTlkkjTjkklkTkjTlkjBABABAiiiiii,證明：斜斜率率單單調(diào)調(diào)減減優(yōu)優(yōu)化化二二：維維護(hù)護(hù)相相鄰鄰決決策策jkl46一類課資一類課資例7.NOI2007貨幣兌換。實(shí)現(xiàn)。時(shí)間復(fù)雜度為尋找最優(yōu)決策用二分來(lái)實(shí)現(xiàn)，維護(hù)序列用平衡樹來(lái)似，實(shí)現(xiàn)與方法三一樣上面的結(jié)論與方法三類nnOln方方法法四四：線線性性規(guī)規(guī)劃劃47一類課資一類課資五.斜率優(yōu)化 這里不再討論。大家能自行分析出來(lái)，有了前面的基礎(chǔ)，相信以上斜率不等式中，或如式。到一個(gè)類似斜率的不等的優(yōu)劣，使參數(shù)分離得比兩個(gè)可選決策狀態(tài)轉(zhuǎn)移方程能通過(guò)對(duì)單調(diào)。i不是單調(diào)的，gixigigxxyyTjjjjjjjj12122121,48一類課資一類課資六、總結(jié)二分來(lái)尋找最優(yōu)決策。隊(duì)首或隊(duì)尾，否則要用最優(yōu)決策在會(huì)增加一個(gè)限制條件，單調(diào)時(shí)，隊(duì)列中的決策斜率不等式中；需要用數(shù)據(jù)結(jié)構(gòu)來(lái)維護(hù)能插在中間，直接插在隊(duì)尾，否則可單調(diào)時(shí)，插入新決策點(diǎn)斜率不等式中g(shù)x補(bǔ)充兩點(diǎn)：49一類課資一類課資