一類單調(diào)問題的求解谷風(fēng)課資

《一類單調(diào)問題的求解谷風(fēng)課資》由會員分享，可在線閱讀，更多相關(guān)《一類單調(diào)問題的求解谷風(fēng)課資（49頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、一類單調(diào)問題的求解中山紀(jì)念中學(xué) 宋新波1一類課資一類課資例0.老徐真人秀做到的？請老徐回答當(dāng)時是怎么通過程序來快速選擇。老徐是編程達(dá)人，決定天的最美味的蘋果。只會吃天數(shù)不超過老徐有個怪癖，每一天干，供同一種美味的蘋果若天，每一天節(jié)目組都提個真人秀，節(jié)目共錄制最美杭城人老徐參加一1061NMMN隨手扔過來下面這個：直接告訴你答案，當(dāng)時老徐是大師，當(dāng)然不會，老徐的做法如下：別為天提供的蘋果美味度分，比如，79,73,78,75,80545MNday180day275day378day473day57980807875，既新鮮又美味，既新鮮又美味808079737978day5-day1=4天天79

2、2一類課資一類課資一.單調(diào)隊列及應(yīng)用 。隊列中的最大值在隊首中維護單調(diào)減的隊列，如例中是單調(diào)減的。素是單調(diào)的，如例由得隊列中保留的元直接刪除。沒有存在的必要，可以比“既新鮮又美味”，跟，且，如果滿足與中，區(qū)間中兩個元素如例右移向右平移的。遞增。查詢區(qū)間是隨著時，非遞減，當(dāng)左邊界遞增，的增加，右邊界。隨著，右邊界中，區(qū)間左邊界如例，天選擇的蘋果的美味度表示老徐第天發(fā)放蘋果的美味度，表示第中，設(shè)如例0 0最最優(yōu)優(yōu)選選擇擇在在隊隊首首：保保持持隊隊列列單單調(diào)調(diào)：去去除除冗冗余余狀狀態(tài)態(tài)：區(qū)區(qū)間間出出現(xiàn)現(xiàn)平平移移：維維護護區(qū)區(qū)間間最最值值：五五大大要要點點：001, 1max01, 1maxmax0a

3、aaaaaallrrlaajjkjkkjiiiiijijkiMiiiMiijMiifiifi3一類課資一類課資一.單調(diào)隊列及應(yīng)用 結(jié)構(gòu)。優(yōu)于堆或線段樹等數(shù)據(jù)時間復(fù)雜度為進出隊列各一次，所以由于每個元素最多只會最優(yōu)答案在隊首插入元素刪除隊首元素刪除隊尾元素中的代碼如下：例,;: ;: );();();()(1:; 0:; 1:0NOendstqaifiienqenincstincthenMstqiifendecdoenqaiaandstenwhilebegindontoiforenst代碼實現(xiàn)：代碼實現(xiàn)：4一類課資一類課資例1.NOIP2010初賽烽火傳遞。，的數(shù)據(jù)，對于的數(shù)據(jù)，對于一行，表示答

4、案。代價。個烽火臺發(fā)出信號所需，表示第行，每行一個數(shù)接下來個發(fā)出信號。個烽火臺中至少要有一表示在連續(xù)表示烽火臺的個數(shù)，。其中第一行：兩個整數(shù)。座城市之間準(zhǔn)確出傳遞襲之時，情報能在這兩少代價，才能使敵軍來請計算總共最少花費多個發(fā)出信號。個烽火臺中至少要有一連續(xù)使情報準(zhǔn)確地傳遞，在號都有一定代價。為了發(fā)出信個烽火臺，每個烽火臺之間有遞軍情，在某兩座城市晚燃燒干柴，以火光傳通過濃煙表達(dá)信息；夜白天燃燒柴草，上。一旦有敵情發(fā)生，般建在險要或交通要道要的軍事防御設(shè)施，一烽火臺又稱烽燧，是重100000100%100;1000%5026521435,WWiiNMNMiNMMNMNMN數(shù)據(jù)范圍：數(shù)據(jù)范圍：樣

5、例輸出：樣例輸出：樣例輸入：樣例輸入：輸出格式：輸出格式：輸入格式：輸入格式：題目描述：題目描述：5一類課資一類課資例1.NOIP2010初賽烽火傳遞 。間復(fù)雜度為使用單調(diào)隊列優(yōu)化，時在隊首。持單調(diào)遞增，最優(yōu)決策，所以隊列中的元素保刪除，可以且，如果而且區(qū)間是向右平移的時要計算區(qū)間最小值，上式計算答案時時程：”得到以下狀態(tài)轉(zhuǎn)移方臺的位置通過考慮“前一個烽火”所需最小代價。個烽火臺一定發(fā)出信號個烽火臺傳遞情報且第表示“在前動態(tài)規(guī)劃：狀態(tài)NOjfjkjfkfifNiMNifAnsMiijMijfMiifjiiifwwii1 ,1maxmin1min分析：分析：6一類課資一類課資例2.GDKOI20

6、09猴子。，：吃到的香蕉數(shù)。個整數(shù)，為猴子最多能輸出只有一行，包含一?？偸俏恢?。并且沒有兩棵樹在同一從近到遠(yuǎn)排列。輸入保證這些樹按照樹到猴子所在樹的距離上的香蕉數(shù)，以及這棵，分別表示每棵香蕉樹個整數(shù)行每行包含兩。下面最多跳躍次數(shù)距離，猴子每次跳躍的最大，分別是香蕉樹的棵數(shù)輸入第一行為三個整數(shù)多能吃多少個香蕉呢？香蕉都吃了。那么它最，它就會把那棵樹上的。每當(dāng)他跳到一棵樹上得太遠(yuǎn)或跳的次數(shù)太多跳力也有限，它不能一次棵樹上。同時猴子的體只想從一棵樹跳到另一它又不想在地上走，而想吃盡量多的香蕉，但棵樹上。這個猴子當(dāng)然則在這排香蕉樹的第一在同一直線上，而猴子蕉樹，這些香蕉樹都種一個猴子找到了很多香100

7、00,5000%100;2000%50;100%3010976543806202550,0DNMNMNMNMDNbabbaiiii數(shù)數(shù)據(jù)據(jù)范范圍圍：樣樣例例輸輸出出：樣樣例例輸輸入入：輸輸出出格格式式：輸輸入入格格式式：題題目目描描述述：7一類課資一類課資例2.GDKOI2009猴子。時間復(fù)雜度為最優(yōu)值在隊首。調(diào)遞減的隊列。移的，可以維護一個單的增加，區(qū)間是向下平值，同一列隨著大列的連續(xù)元素的區(qū)間最時需要計算第，計算按照列從小到大來處理答案時且其中時：得到以下狀態(tài)轉(zhuǎn)移方程點考慮最后一次跳躍的起。棵樹最多能吃多少香蕉次跳躍跳到第棵樹不超過表示從第動態(tài)規(guī)劃：狀態(tài)NMOijjifMNfAnsjDik

8、jkfijifkijjifbbaakii1, 11101,max0,1,0分析：分析：ij-1j8一類課資一類課資例3.多重背包且價值總和最大。不超過背包容量，使這些物品的體積總和。選擇物品裝入背包可價值是，件可用，體積是種物品最多有的背包。第種物品和一個容量為有wvmiiiiVN9一類課資一類課資例3.多重背包：分別用藍(lán)色和紅色標(biāo)記要用到的元素示意圖，和觀察計算這里不做介紹當(dāng)然用倍增法優(yōu)化到時間復(fù)雜度為下狀態(tài)轉(zhuǎn)移方程：個物品裝幾個”得到以通過考慮“第值。個物品能獲得的最大價的背包來裝前表示用容量為背包問題，定義狀態(tài)vmvmwviNiNiiiiiijifjifmVOVOjxxxjifijifi

9、ijjifi,*,*,min0*, 100,121log分析：分析：iji-1j-vij+vi10一類課資一類課資例3.多重背包NVOjjikkkjifkkkjifkkkjifjifkjifjifjifjifjifjifjifvvvxxxwxvxvwxvxvxxxvxvxwxvxwxvxxxxxvviiiiiiiiiiiiiiiii時間復(fù)雜度為空間。的值分批次處理以節(jié)省按照模當(dāng)然也可以把的狀態(tài)等于模對應(yīng)背包容量個單調(diào)隊列，其中隊列建立一行來做，每一行需要從小到大來處理，一行按可以永久刪除。優(yōu)，還是比的，跟上面的不等式是等價，而不等式對應(yīng)著同樣的可選決策對應(yīng)著的可選決策來說于后面的某一個狀態(tài)可以

10、直接刪除。因為對時，且滿足：如果時，對于兩個可選決策計算在向右平移；區(qū)間相對時涉及到的元素組成的計算等距的元素，距離為時涉及的元素是上一行置連續(xù)的元素，如計算注意這里的區(qū)間不是位：活運用單調(diào)隊列來優(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)平移：維護區(qū)間最值：維護區(qū)間最值：分析：分析：11一類課資一類課資例4.HNOI2008Toy1072,1 ,50000141243145118ccLxcciijikkiLNNLNLPLxPijxjiPODZiN

11、NPODZODZPP數(shù)據(jù)范圍：數(shù)據(jù)范圍：樣例輸出：樣例輸出：樣例輸入：樣例輸入：輸出格式：輸出格式：輸入格式：輸入格式：題目描述：題目描述：輸出最小費用。行輸入，接下來和第一行輸入兩個整數(shù)，但他希望費用最小。甚至超過意長度的容器，他可以制造出任教授不關(guān)心容器的數(shù)目是一個常量。，其中，其制作費用為度為授的研究，如果容器長教器長度有關(guān)，根據(jù)。制作容器的費用與容，那容器的長度將為件玩具放在一個容器中到第如果將第形式地說，個單位長度的填充物。玩具之間要加入個玩具，那么相鄰兩件果一個一維容器中有多號是連續(xù)的。同時，如器中的玩具編教授要求在一個一維容。為了方便整理，處理后一維長度是件玩具經(jīng)過件玩具，第的到

12、號為教授有編一維容器中。維，再裝到一種特殊的可以將任意物品變成一來給玩具裝箱。自己的物體維度壓縮器教授使用北京去。決定把所有玩具都運到堆智力玩具。于是，他他割舍不下自己的一大教授要去看奧運，但是月12一類課資一類課資例4.HNOI2008Toy ，超時。直接做時間復(fù)雜度為入的分析。的單調(diào)性，需要深就可以刪除”這樣明顯沒有前面幾個例子中“卻沒有分離，的，這兩個參數(shù)是完全分離和這三項中式子中則有對應(yīng)的費用記為。可選決策定義離注意展開過程中參數(shù)分，是未知的，展開平方式的含有這些量相當(dāng)于已知，而時，計算其中下狀態(tài)轉(zhuǎn)移方程：這段連續(xù)的玩具，得以到設(shè)是裝在同一個容器中，假考慮哪些玩具與玩具的前綴和。為用，

13、個玩具裝箱所需最小費表示把前動態(tài)規(guī)劃：狀態(tài)njififjjigjxigjxjxigififLjsisjicOjjjxigjijfjxigjfjfjjsjjxLisiigjsjjfjLisiifijjfifijiisiifjji2112222222,*2,1*211,1,1,1,1,1min121分析：分析：13一類課資一類課資例4.HNOI2008Toy 斜率優(yōu)化！題要用到新知識：兩個點形成的斜率，這，上面式子左邊像：是單調(diào)遞增的，所以有因再令jjjjjjixjjjxjjxjigjjxjigjjxjigxxyyisiixifiyxxigffxigfxigf2112122122122212122

14、22*2)()()()(1,1*211-21*211*221的前提條件：的前提條件：j jj j時時研究研究i if fi if fj jj j1 12 21 12 214一類課資一類課資例4.HNOI2008Toy 的結(jié)論：增的。下面有兩個重要都是單調(diào)的，都是單調(diào)和該題則必須滿足優(yōu)，令比，如果時，可選決策計算igixigTxxyyTifjjjjjjjjjjjj*2,)()()()(,211212211212斜斜率率優(yōu)優(yōu)化化： 再繼續(xù)維護！列基礎(chǔ)上加入新的決策時可以在之前維護的隊并且在是最優(yōu)的！優(yōu)。所以隊首比優(yōu)，比優(yōu)，比來說，則對于所以可以刪除。優(yōu)，永遠(yuǎn)比時，有：，計算后面的是單調(diào)增的，則對于

15、由于之間的斜率策如果隊列中相鄰兩個決。，, 11.,*2,.,*2,*2,*2*2,*2,*2,.,*2,*2,*2,.,11322113221111111322121iififigTigTigTxxygigyxTfiigigyxTyxigTigTigTigifjjjjjjjjjjjjjiiiijjjjjjjjjjkkkkkkk證證明明：最最優(yōu)優(yōu)決決策策是是隊隊首首元元素素即即：的的斜斜率率都都要要大大于于使使得得這這些些相相鄰鄰決決策策之之間間決決策策依依次次存存儲儲有有價價值值的的可可選選大大策策，使使得得隊隊列列中中從從小小到到可可以以刪刪除除其其中中的的冗冗余余決決 到到i i, ,時

16、時，所所有有可可選選決決策策是是1 1結(jié)結(jié)論論1 1：計計算算15一類課資一類課資例4.HNOI2008Toyj1j2j3 可以刪除。得證！不可能成為最優(yōu)決策，出現(xiàn)了矛盾！所以優(yōu)比優(yōu)比。的過程中成為最優(yōu)決策有沒有可能在計算，分析即。鄰斜率單調(diào)遞減的情況，假設(shè)出現(xiàn)下圖所示相設(shè)隊列中三個相鄰決策jjjjjjjjjjjjjjjjjjjjjTigTigTigTfTT221323232211223221321,*2,*2,*2,證明：證明：決策之間的斜率單調(diào)增決策之間的斜率單調(diào)增結(jié)論2：可以維護相鄰結(jié)論2：可以維護相鄰 最最優(yōu)優(yōu)決決策策取取隊隊首首元元素素策策滿滿足足：應(yīng)應(yīng)該該維維護護隊隊列列中中相相鄰

17、鄰決決綜綜上上：jjjjjjkkTTTig,.,*21322116一類課資一類課資例4.HNOI2008Toy ：最優(yōu)決策在隊首。；或者于直到隊列中元素個數(shù)小，循環(huán)做下去，則刪除隊首元素，如果取隊首兩個決策加入隊尾；：把新的可選決策或者列中的元素個數(shù)小于。循環(huán)做下去，直到隊則刪除隊尾元素如果策每次選隊列最后兩個決要插入新的可選決策取取頭頭刪刪頭頭：插插入入刪刪尾尾：igTigTiiTTiTTijjjjjjjjjjjjjjjjkkkkkkkkk*2,2*2,2,2112121111 步：下所以具體程序?qū)崿F(xiàn)分以遞增由于，坐標(biāo)是插入點，相當(dāng)于在二維平面中插入一個新的決策計算枚舉維護相鄰決策滿足：的整

18、個過程中，始終要在計算4,.,*213221ixiyixiiifiTTTigfjjjjjjkk程序?qū)崿F(xiàn)：程序?qū)崿F(xiàn)：17一類課資一類課資例4.HNOI2008Toy動畫演示：動畫演示：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時間復(fù)雜度為取頭刪頭插入去尾

19、;);,(cos 1: );()*2)1,() 1( ;: );();(),),1() 1(1:; 0:; 1:; 0: 0程序代碼：程序代碼：19一類課資一類課資例5.APIO2010特別行動隊的戰(zhàn)斗力和更大。正后，沒有其他方案能使修。修正后的戰(zhàn)斗力和為為，修正后的戰(zhàn)斗力分別戰(zhàn)斗力分別為。特別行動隊的初始，第三隊包含士兵，第二隊包含士兵和士兵含士兵特別行動隊：第一隊包個士兵組成。此時，最佳方案是將。經(jīng)驗公式中的參數(shù)為名士兵，和。例如你有最大。試求出這個最大動隊修正后戰(zhàn)斗力之和編隊，使得所有特別行你要為這支部隊進行。作為部隊統(tǒng)帥，現(xiàn)在是已知的系數(shù)其中式修正為將按如下經(jīng)驗公的初始戰(zhàn)斗力總結(jié)出一支

20、特別行動隊。通過長期的觀察，你之和，即為對內(nèi)士兵初始戰(zhàn)斗力戰(zhàn)斗力一支特別行動隊的初始的士兵的初始戰(zhàn)斗力為編號為的序列。即為形如隊員的編號應(yīng)該連續(xù)，同一支特別行動隊中戰(zhàn)場。出于默契的考慮若干特別行動隊調(diào)入編號，要將他們拆分成到隊，士兵從名預(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 xi

21、cbannn數(shù)據(jù)范圍：數(shù)據(jù)范圍：20一類課資一類課資例5.APIO2010特別行動隊 分。可以得直接做，時間復(fù)雜度為其中。和這一項無法分離令盡量分離得：和未知。把已知，展開得其中則有：移，假設(shè)是的士兵”來進行狀態(tài)轉(zhuǎn)個士兵在同一個行動隊通過考慮“跟第的前綴和。為戰(zhàn)斗力修正戰(zhàn)斗力。別行動隊能獲得的最大個士兵拆分成若干個特表示把前動態(tài)規(guī)劃：狀態(tài)50,1,1*2max1*2*,1*1*1*21*11*1*2*1:1,1*1max,222222221111nisjsisjsjsisjsisxOijjsisaihjgifjijsisacisbaihjsbajfjgcisbajsisajsbajfjijic

22、jsbisbajsisaajfijcjsisbajfifjiisiifi分析：分析：21一類課資一類課資例5.APIO2010特別行動隊 上一題用斜率優(yōu)化！是單調(diào)的，可以考慮像的坐標(biāo)是的坐標(biāo)是中兩個點形成的斜率，其，上面式子左邊像上式得：是單調(diào)增的是正整數(shù)，因初始戰(zhàn)斗力：時isgsgsisassggisssisaggsisaihgsisaihgjjjjjjjjjjjjjjxxjjjjjjjjififjjijji22211121121211212112212,1,1*21111*21*21*212的前提條件的前提條件研究研究22一類課資一類課資例5.APIO2010特別行動隊 個重要的結(jié)論：是單

23、調(diào)增的，同樣有兩該題優(yōu)，必須滿足要比時換句話說，優(yōu)，必須滿足比。如果，令時，可選決策根據(jù)上面分析：計算isisaTisaTssggTifjjjjjjjjjjjjjjjjjj*2,*2,11,212121211212122112應(yīng)用斜率優(yōu)化：應(yīng)用斜率優(yōu)化： 是最優(yōu)的！優(yōu)。所以隊尾元素比，優(yōu)，比優(yōu)，比所以可以刪除優(yōu)，永遠(yuǎn)比時，有：，計算對于后面的是單調(diào)增的，優(yōu)。由于比之間的斜率策如果隊列中相鄰兩個決。，jjjjjjjjjjjjjiiiijjjjjjjjjjkkkkkkkkkisaTisaTisaTyyxsaisayxTfiisyxisayxTyxisaTisaTisaTisaif1 -231213

24、22111111322121.*2,.,*2,*2,*2*2,*2,*2,.,*2,*2,*2,.,證證明明：最最優(yōu)優(yōu)決決策策是是隊隊尾尾元元素素即即：大大于于相相鄰鄰決決策策之之間間的的斜斜率率都都依依次次存存儲儲可可選選決決策策，使使得得隊隊列列中中從從小小到到大大時時，可可以以刪刪除除冗冗余余決決策策結(jié)結(jié)論論1 1：計計算算23一類課資一類課資例5.APIO2010特別行動隊 可以刪除。得證！不可能成為最優(yōu)決策，出現(xiàn)了矛盾！所以優(yōu)比優(yōu)比。的過程中成為最優(yōu)決策有沒有可能在計算，分析即。鄰斜率單調(diào)遞增的情況，假設(shè)出現(xiàn)下圖所示相設(shè)隊列中三個相鄰決策jjjjjjjjjjjjjjjjjjjjjTi

25、saTisaTisaTfTT232213232211223221321,*2,*2,*2,證明：證明：決策之間的斜率單調(diào)減決策之間的斜率單調(diào)減結(jié)論2：可以維護相鄰結(jié)論2：可以維護相鄰 最最優(yōu)優(yōu)決決策策取取隊隊尾尾元元素素策策滿滿足足：應(yīng)應(yīng)該該維維護護隊隊列列中中相相鄰鄰決決綜綜上上：isaTTTjjjjjjkk*2,.,1322124一類課資一類課資例5.APIO2010特別行動隊 ?？倳r間復(fù)雜度為：最優(yōu)決策在隊尾。；或者個數(shù)小于下去，直到隊列中元素，循環(huán)做，則刪除隊尾元素，如果取隊尾兩個決策加入隊尾；：把新的可選決策或者列中的元素個數(shù)小于。循環(huán)做下去，直到隊則刪除隊尾元素如果策每次選隊列最后

26、兩個決要插入新的可選決策nOisaTisaTiiTTiTTijjjjjjjjjjjjjjjjkkkkkkkkkkkkkkkk取取尾尾刪刪尾尾：插插入入刪刪尾尾：*2,2*2,2,111111 步：分以下遞增所以具體程序?qū)崿F(xiàn)由于，坐標(biāo)是插入點，相當(dāng)于在二維平面中插入一個新的決策計算枚舉維護相鄰決策滿足：的整個過程中，始終要在計算4,1,*2,.,13221ixigisiiifiisaTTTfjjjjjjkk程序?qū)崿F(xiàn)：程序?qū)崿F(xiàn)：25一類課資一類課資二.斜率優(yōu)化總結(jié) 都是單調(diào)的。和以上斜率不等式中是后加入的決策點設(shè)為了便于分析，我們假或如的不等式：到關(guān)于斜率的優(yōu)劣，使參數(shù)分離得對比兩個可選決策狀態(tài)轉(zhuǎn)

27、移方程能通過igixigxxyyigxxyyTjjjjjjjjjjjjjjj221121212122121,兩個使用前提：兩個使用前提：26一類課資一類課資二.斜率優(yōu)化總結(jié) 。，最優(yōu)決策取隊首元素滿足：維護隊列中的相鄰決策單調(diào)減：，最優(yōu)決策取隊尾元素滿足：維護隊列中的相鄰決策單調(diào)增：，最優(yōu)決策取隊尾元素滿足：維護隊列中的相鄰決策單調(diào)減：，最優(yōu)決策取隊首元素滿足：維護隊列中的相鄰決策單調(diào)增：，種情況：的單調(diào)性”分為以下四”和“還是經(jīng)總結(jié)，根據(jù)“jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjkkkkkkkkTTTigigigTigTTTigigTigTTTigigTTTT

28、igigigTgigTigT,.,;,.,;,.,;,.,13221211322121132212113221212121,四種情況：四種情況：27一類課資一類課資三.斜率優(yōu)化 。是單調(diào)的，以上斜率不等式中或如式。到一個類似斜率的不等的優(yōu)劣，使參數(shù)分離得比兩個可選決策狀態(tài)轉(zhuǎn)移方程能通過對不是單調(diào)的i但gixigigxxyyTjjjjjjjj12122121,28一類課資一類課資例6.游戲 慶語其慶語其驗學(xué)校驗學(xué)校出題人：北師大附屬實出題人：北師大附屬實數(shù)據(jù)范圍：數(shù)據(jù)范圍：樣例輸出：樣例輸出：樣例輸入：樣例輸入：輸出格式：輸出格式：輸入格式：輸入格式：題目描述：題目描述：。的數(shù)據(jù)，對于的數(shù)據(jù)，對

29、于最多能得到的分?jǐn)?shù)。一個整數(shù)，表示。個數(shù)表示其中第個整數(shù)。第二行有第一行一個整數(shù)分。想知道他最多能得多少，沒有分。有分?jǐn)?shù)。他現(xiàn)在在原點上的所有分?jǐn)?shù)，原點沒現(xiàn)給出上。，他最后必須停在點上的分?jǐn)?shù)，且要求是其中的分?jǐn)?shù)，他將得到頂?shù)巾敚瑫r如果他從游戲里他只能向正方向他在玩一個游戲，這個頂?shù)饺我庹c上。現(xiàn)在頂?shù)礁h(yuǎn)的地方，他能的頭變多了，于是他能現(xiàn)在內(nèi)的數(shù)軸上的整點上。之隔在整點可以頂?shù)脚c自己相化到數(shù)軸上，即從一個點上。我們現(xiàn)在將之簡一個整點頂?shù)搅硪粋€整的位移，也就是從頂出前水平有限，每次只能是會造成位移的。他之從小就愛亂頂，但是頂500 ,100000%100;1000%6050111503,1)(

30、*,jannWYFiainnWYFnnijjjaijjajiWYFkkWYF29一類課資一類課資例6.游戲 jjjjjjjjjjjjjjjjjjjjjjjnkkkTTTiaxxfxxiaffTiaiiafiaiiafjiiajOijjiiajfifijiif,.,.,1,*600 ,*max1322121121221112212212要滿足：可選決策隊列中從小到大排列的。即：之間的斜率是單調(diào)減的法可以得出，相鄰決策采用前面兩題類似的方還是有的！策之間的斜率的單調(diào)性就不存在了，但相鄰決中的結(jié)論類似于斜率優(yōu)化不是單調(diào)的！是遞增的，但橫坐標(biāo)的坐標(biāo)是形式，決策不等式左邊也是斜率的優(yōu)？比，什么情況下策沒

31、有分離，考慮兩個決和，有一項是分。，直接做時間復(fù)雜度為方程：的，得到以下狀態(tài)轉(zhuǎn)移頂?shù)娇紤]最后一次是從的最大得分。表示從原點頂若干次到動態(tài)規(guī)劃：分分析析：30一類課資一類課資例6.游戲 nnOiaTiaTTTTiaiaTiaTTTiaTifjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjxxxxxxxkxxxkkxxxxxxxxxxxxxxxxxkln,.,.,.,.,.,11211211111211322111 -21時間復(fù)雜度為法就可以找出率是單調(diào)減的，用二分因為相鄰決策之間的斜就是最優(yōu)決策，且滿足因此只要都要優(yōu)！比后面的優(yōu)比都要優(yōu)！比前面的優(yōu)比。則有：假設(shè)最優(yōu)

32、決策是時隊列中可選決策有計算分分法法求求最最優(yōu)優(yōu)決決策策方方法法一一：二二31一類課資一類課資例6.游戲 nnOlrxlyrjjjjllryllrxkrljjjififififififyxyxjjln312111,131*2131, 1,是的區(qū)間，時間復(fù)雜度也每次排除否則回到則直接比較找出答案，如果否則則如計算，取一開始可以使用三分法：峰的模型，單峰求極值所有決策點形成一個單在二維平面中畫出點作為縱坐標(biāo)，對應(yīng)的得分作為橫坐標(biāo)，把決策把隊列中的可選決策：三三分分法法求求最最優(yōu)優(yōu)決決策策方方法法二二好點好點壞點壞點32一類課資一類課資例6.游戲的時間復(fù)雜度也是值計算一次決策點對應(yīng)的的區(qū)間，每次三分

33、只需每次刪除即：右的決策點。在新的有效區(qū)間中是靠右邊的無效區(qū)間，是壞點，刪除如果左的決策點；在新的有效區(qū)間中是靠左邊的無效區(qū)間，是壞點，刪除如果并滿足以下兩個要求：的比例固定，與和靠右決策點選擇靠左決策點長度為另一種三分法，總區(qū)間：nOllylxyxlyxlxylxxyyyxxlyxyxlln*25-3*215*25-3,黃黃金金分分割割三三分分法法求求最最優(yōu)優(yōu)決決策策方方法法三三Lxy33一類課資一類課資四.斜率優(yōu)化 或最左邊策點不一定插在最右邊不單調(diào)時，插入新的決。但以上斜率不等式中或如式。到一個類似斜率的不等的優(yōu)劣，使參數(shù)分離得比兩個可選決策狀態(tài)轉(zhuǎn)移方程能通過對ixigigxxyyTjj

34、jjjjjj都不是單調(diào)的i和gix12122121,34一類課資一類課資例7.NOI2007貨幣兌換券。次賣出操作賣出所有金操作使用完所有錢；每賣方案滿足：每次買進必然存在一種最優(yōu)的買，：位小數(shù)。答案保留得的最大的金錢數(shù)目。天的操作結(jié)束時能夠獲，表示第只有一個實數(shù)。、行三個實數(shù)行，第接下來時擁有的錢數(shù)。能預(yù)知的天數(shù)以及初始分別表示小、第一行兩個正整數(shù)元錢。天后最多能夠獲得多少元錢，那么，如果開始時擁有他還希望能夠計算出來。券的價值以及券和天內(nèi)的經(jīng)知道了未來運作和行情測算，他已員工，通過較長時間的時一個很有經(jīng)濟頭腦的小行多次操作。注意：同一天內(nèi)可以進；天恰好為例在第券的比券和供給顧客的的金券，并

35、且，滿足提兌換給用戶總價值為元人民幣，交易所將會買入金券：顧客支付為人民幣；券以當(dāng)時的價值兌換的券和的為：將作為賣出比例，其意義內(nèi)的實數(shù)個賣出金券：顧客提供一兩個方面：易法。比例交易法分為便的交易方式：比例交易所提供了一種非常方為了方便顧客，金券交。單位金券元和券的價值分別為券和天中第人民幣數(shù)目。我們記錄位金券當(dāng)天可以兌換的當(dāng)時的價值，即每一單動，兩種金券都有自己每天隨著市場的起伏波數(shù)。券的數(shù)目可以是一個實有一個自己的賬戶。金每個持有金券的顧客都。券以前簡稱紀(jì)念券和券以下簡稱紀(jì)念券發(fā)行交易兩種金券：工作。該金券交易所只最近在一家金券交易所小提提示示：數(shù)數(shù)據(jù)據(jù)規(guī)規(guī)模模和和約約定定：輸輸出出格格式

36、式：輸輸入入格格式式：題題目目描描述述：109,1000 ,100100 ,000100%100;1000%60;10%403,)%100, 0)/()()(MaxprofitNNNNMaxprofitKNYSNNSRateBANYKBAIPIPbBOPAOPOPaBAkBBAAYRateBARateBARateBAkkkkkkkkk35一類課資一類課資例7.NOI2007貨幣兌換錢？天后用戶最多擁有多少元錢，問初始時用戶擁有。兩種金券的比例為、值的金券，買入的用所有的錢買入等價賣出所有的金券；如下操作：每一天用戶進行若干次、分別具有單位價值、天天內(nèi)，第接下來的兩種金券進行交易。、金券交易所可

37、以對NSBABAiNBARateBAiii,問問題題簡簡述述：么不賣要么全賣。操作也是完全的，即要類似的，可以證明賣出么不買要么全部買進；也就是說，買進操作要能使獲利最大化時，取當(dāng)能使獲利最大化時，取當(dāng)，則最后總利潤買進時使用錢的比例為。利為一元錢不買金券最后獲券到最后會獲利為券和元，假定一元錢買進的，假設(shè)有在進行買進操作的時候01*1*,xqpxqpxqpqSqxSpxSxqpBAS提示的證明：提示的證明：36一類課資一類課資例7.NOI2007貨幣兌換 分。，間復(fù)雜度為可以用搜索來解決，時全部賣出進全部賣出后再全部買全部買進不進行活動種：動有以下出每一天可能進行的活根據(jù)上面的提示，總結(jié)40

38、4nO4 4方方法法一一：搜搜索索37一類課資一類課資例7.NOI2007貨幣兌換 分。，直接做時間復(fù)雜度為時下狀態(tài)轉(zhuǎn)移方程：根據(jù)上面的分析，得以獲利”這個子問題。天的最大第天賣出，這就涉及到“再在第天的最大獲利全部買入第這樣實際上就是要求把沒有進行任何操作。天到第天，即第一次買入操作發(fā)生在第全部賣出：假設(shè)最后；進：這種操作沒有意義全部賣出后再全部買沒有意義；全部買進：這種操作天的最大獲利；利等于第不進行活動：最大獲天可以進行的活動：考慮第天的最大獲利表示前狀態(tài)601*1max1,1111,2nBARateBARateOijjfifiSifjNjNjjiiSfiifjjjiij方方法法二二：動

39、動態(tài)態(tài)規(guī)規(guī)劃劃38一類課資一類課資例7.NOI2007貨幣兌換 jjjjjjjjjRateRatejRatejjjABjjRatejRatejjjjjjjBARatejRatejBjARatejBjARatejjjjjBARateBARateBARateBARatekkkjiiiiiiiiiijjjjjjjiijTTTjgjgjjgjgggggjgjgTggjgggjgjggjggjgjgjgjfjgjijf,.,.,*,*,*,*11,*132212112121212211221121122122112121212，利用前面所學(xué)易知：序列標(biāo)從小到大排序得決策把所有決策點按照橫坐，縱坐標(biāo)是的橫

40、坐標(biāo)是的形式，決策點以上不等式左邊是斜率時，得：時，得：沒有單調(diào)性：更優(yōu)？比什么情況下、分析兩個決策則上式設(shè)枚舉到因為要從這里以上方程主要慢在方方法法三三：斜斜率率優(yōu)優(yōu)化化39一類課資一類課資例7.NOI2007貨幣兌換分。，時間復(fù)雜度為介紹。中的二分法，這里不再可以采用例不單調(diào)，尋找最優(yōu)決策因為都可以?；蚩梢杂闷胶鈽鋪砭S護，。右邊的維護類似。或者滿足個決策點少于，重復(fù)執(zhí)行直到左邊的則刪除，如果的前一個決策點和決策點的前一個次找其中左邊的維護可以每要保證斜率是遞減的，的左邊和右邊，兩邊都并分別維護插入不用插入，否則進行出現(xiàn)了斜率上升，如果右邊的決策左邊的決策找到的操作如下：插入一個新決策間的斜

41、率單調(diào)遞減！然后再維護相鄰決策之中間，尾，有可能會插在隊列點時不可以直接插在隊不單調(diào)時，插入新決策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)動畫演示：動畫演示：41一類課資一類課資例7.NOI2007貨幣兌換 yBxABARateyBARateRatexBARateBARatejijijjjjjj

42、jjjjjjiijjjfjfjfif*,*max對應(yīng)的獲利，決策令方方法法四四：線線性性規(guī)規(guī)劃劃42一類課資一類課資例7.NOI2007貨幣兌換天的價值都是一樣的；直線上每一個點在第，恰好為獲利的軸的截距為直線在直線方程為：的直線，過這個點作一條斜率為在二維平面上對應(yīng)著點決策iyxyxyjBByBxAByBxABABAxyBAyxiijijiijijiiiiijjiijj1*,幾幾何何意意義義：43一類課資一類課資例7.NOI2007貨幣兌換 決策。離原點最遠(yuǎn)的就是最優(yōu)所有交點中的直線條斜率為的直線，再過原點作一為過每個決策點作斜率平面上的點；天購買金券對應(yīng)到二維在第時的獲利”計算就是用“使用

43、決策的直線，兩直線的交點過原點作一條斜率為,11RateBARateiiiiiifj幾幾何何意意義義：最優(yōu)決策最優(yōu)決策44一類課資一類課資例7.NOI2007貨幣兌換的優(yōu)劣情況：和決策分析決策連線的斜率為和點點假設(shè)增加而減少隨著得決策點的降序排序，維護序列使相同時按照升序，把所有決策按照kjkjTkjxyyxxxxkj,斜斜率率單單調(diào)調(diào)減減優(yōu)優(yōu)化化二二：維維護護相相鄰鄰決決策策優(yōu)優(yōu)化化一一：去去除除冗冗余余BAiikjT,jkRateixy 直線 決策j與k一樣優(yōu),kj,T1BAiijkRateixy 直線 決策k更優(yōu),kj,T2BAiijkRateixy 直線 決策j更優(yōu),kj,T3BAii

44、45一類課資一類課資例7.NOI2007貨幣兌換策，可以刪除。得證！永遠(yuǎn)不可能成為最優(yōu)決決策產(chǎn)生矛盾。，與前面的假設(shè)優(yōu)比優(yōu)比根據(jù)上面的分析：優(yōu)決策將來有沒有可能成為最在這種情況下現(xiàn)在包括考慮決策，即如下圖所示。滿足假設(shè)三個相鄰的決策klkTkjTkjTlkTlkTlkkjTjkklkTkjTlkjBABABAiiiiii,證明：斜斜率率單單調(diào)調(diào)減減優(yōu)優(yōu)化化二二：維維護護相相鄰鄰決決策策jkl46一類課資一類課資例7.NOI2007貨幣兌換。實現(xiàn)。時間復(fù)雜度為尋找最優(yōu)決策用二分來實現(xiàn)，維護序列用平衡樹來似，實現(xiàn)與方法三一樣上面的結(jié)論與方法三類nnOln方方法法四四：線線性性規(guī)規(guī)劃劃47一類課資一類課資五.斜率優(yōu)化 這里不再討論。大家能自行分析出來，有了前面的基礎(chǔ)，相信以上斜率不等式中，或如式。到一個類似斜率的不等的優(yōu)劣，使參數(shù)分離得比兩個可選決策狀態(tài)轉(zhuǎn)移方程能通過對單調(diào)。i不是單調(diào)的，gixigigxxyyTjjjjjjjj12122121,48一類課資一類課資六、總結(jié)二分來尋找最優(yōu)決策。隊首或隊尾，否則要用最優(yōu)決策在會增加一個限制條件，單調(diào)時，隊列中的決策斜率不等式中；需要用數(shù)據(jù)結(jié)構(gòu)來維護能插在中間，直接插在隊尾，否則可單調(diào)時，插入新決策點斜率不等式中g(shù)x補充兩點：49一類課資一類課資