【正文】 安排，成功地對(duì)于每一次加強(qiáng)的題目都設(shè)計(jì)出了優(yōu)秀的算法，下面，我們來(lái)看一看“順序”的合理安排的例子：［例二］樹(shù)的果實(shí)【題意描述】給出一棵有N個(gè)節(jié)點(diǎn)的有根樹(shù)（根為1號(hào)節(jié)點(diǎn)），每個(gè)節(jié)點(diǎn)有權(quán)值。時(shí)間復(fù)雜度為O(Nlog2(N))。這樣，我們得到了復(fù)雜度為O(Nlog2(N))的算法。也就是說(shuō)，一個(gè)重連通分量可以當(dāng)作整體來(lái)考慮。我們只需要將幾個(gè)有關(guān)的塊進(jìn)行合并。在細(xì)節(jié)實(shí)現(xiàn)中，我們又利用了樹(shù)的兩大遍歷序——中序遍歷和前序遍歷，把樹(shù)上的求LCA操作和提升子樹(shù)的操作變成了序列上的求RMQ操作和給一個(gè)區(qū)間所有元素減去一個(gè)值的操作。打印機(jī)，掃描儀 m　?。ㄆ渲蠳（32000）表示總錢數(shù)，m（60）為希望購(gòu)買物品的個(gè)數(shù)。【輸入樣例】411123413【輸出樣例】2 0 00 0 00 3 10 1 1航線規(guī)劃 NOI2005安徽省隊(duì)選拔賽題目【題目描述】對(duì)Samuel星球的探險(xiǎn)已經(jīng)取得了非常巨大的成就，于是科學(xué)家們將目光投向了Samuel星球所在的星系——一個(gè)巨大的由千百萬(wàn)星球構(gòu)成的Samuel星系。C為1表示詢問(wèn)當(dāng)前星球A和星球B之間有多少條關(guān)鍵航線；C為0表示在星球A和星球B之間的航線被破壞，當(dāng)后面再遇到C為1的情況時(shí)，表示詢問(wèn)航線被破壞后，關(guān)鍵路徑的情況，且航線破壞后不可恢復(fù)； C為1表示輸入文件結(jié)束，這時(shí)該行沒(méi)有A,B的值。輸入：第一行有兩個(gè)整數(shù)N，M。遺憾的是果樹(shù)可能很龐大，而小蟲(chóng)幾乎是不會(huì)計(jì)算的，身為程序員的你幫幫他們吧。他希望在不超過(guò)N元（可以等于N元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。主件利用線段樹(shù)或樹(shù)狀數(shù)組我們就可以用O(log2(N))的時(shí)間完成這項(xiàng)操作。我們思考怎么處理這個(gè)問(wèn)題：刪邊操作會(huì)導(dǎo)致塊的分裂。我們繼續(xù)思考：樹(shù)上的任意兩點(diǎn)間只有一條路徑。我們一個(gè)很巧妙的方法：從大到小地向線段樹(shù)里面加入元素，然后統(tǒng)計(jì)區(qū)間個(gè)數(shù)。這正是我們比較熟悉的序列上的統(tǒng)計(jì)問(wèn)題。而在線形的序列上，沒(méi)有用的錢自然地被分配給后面的元素。但是這樣有什么好處嗎？還能進(jìn)行動(dòng)態(tài)規(guī)劃嗎？怎樣設(shè)計(jì)狀態(tài)才能傳遞父節(jié)點(diǎn)的狀態(tài)呢？我們?cè)倩剡^(guò)去看算法3的狀態(tài)轉(zhuǎn)移：假設(shè)當(dāng)前狀態(tài)是F[i][j][k]，且k=0。我們是否有合理的組織數(shù)據(jù)的辦法呢？【數(shù)據(jù)組織方案三】重新安排這些物品的順序，使得每個(gè)附件都緊跟其主件，保證其左邊的第一個(gè)主件就是它附屬的主件。我們回到題目并考慮其特殊性：。對(duì)數(shù)據(jù)組織的合理化，不僅在我們?cè)O(shè)計(jì)算法時(shí)能起到優(yōu)化程序效率的作用，有時(shí)，我們?cè)诮⒔忸}模型時(shí)，合理地組織數(shù)據(jù)可能給我們提供新的思考角度，從而優(yōu)化解題模型，例一就是這樣的一個(gè)例子。對(duì)數(shù)據(jù)進(jìn)行合理地組織，正是我們面對(duì)上述題目時(shí)的一種有效手段。但是題目與背包卻有一些差別：附件不能被直接購(gòu)買。weight[i][k]表示分組后第i個(gè)對(duì)象的第k種購(gòu)買方案的總權(quán)值。分情況進(jìn)行狀態(tài)轉(zhuǎn)移：情況I：第i個(gè)物品是主件F[i][j][k]=Max{F[i+1][jcost[i]][1]+weight[i] (j=cost[i]),F[i+1][j][0]}情況II：第i個(gè)物品是附件 如果k=1 F[i][j][k]= Max{F[i+1][jcost[i]][1]+weight[i] (j=cost[i]),F[i+1][j][1]} 如果k=0 F[i][j][k]= F[i+1][j][0]狀態(tài)總數(shù)：O(NM)轉(zhuǎn)移代價(jià)：O(1)時(shí)間復(fù)雜度同樣是O(NM)。這一結(jié)論似乎很顯然，但是我們并不是要在樹(shù)結(jié)構(gòu)中用這一結(jié)論。要求對(duì)于每一個(gè)節(jié)點(diǎn)，求：其中(1=N=105)【問(wèn)題分析】對(duì)于要求的后面兩個(gè)值，我們很容易想到O(Nlog2(N))的算法：樹(shù)上除其子孫節(jié)點(diǎn)外比該節(jié)點(diǎn)大的節(jié)點(diǎn)總數(shù)：直接排序，在待統(tǒng)計(jì)節(jié)點(diǎn)前的與該節(jié)點(diǎn)權(quán)值不同的個(gè)數(shù)再減去問(wèn)題1的答案即為所求。假設(shè)現(xiàn)在我們要統(tǒng)計(jì)一個(gè)區(qū)間(長(zhǎng)度為L(zhǎng))。WC2005何林同學(xué)的論文中介紹了此題的另一解法，復(fù)雜度也為O(Nlog2(N))?！境醪浇M織數(shù)據(jù)】由前面的思考，我們把圖中的重連分量都“縮”成一個(gè)點(diǎn)。換句話說(shuō)，就是把一些點(diǎn)的位置抬高，并把它們合并成一個(gè)塊。無(wú)處不體現(xiàn)出“對(duì)數(shù)據(jù)的合理組織”。書柜）　　從第2行到第m+1行，第j行給出了編號(hào)為j1的物品的基本數(shù)據(jù)，每行有3個(gè)非負(fù)整數(shù)　　v星際空間站的Samuel II巨型計(jì)算機(jī)經(jīng)過(guò)長(zhǎng)期探測(cè)，已經(jīng)鎖定了Samuel星系中許多星球的空間坐標(biāo)，并對(duì)這些星球從1開(kāi)始編號(hào)3……。被破壞的航線數(shù)目與詢問(wèn)的次數(shù)總和不超過(guò)40000?，F(xiàn)在請(qǐng)你幫助完成。他們以此來(lái)選擇最終要被咬掉的果子是哪一個(gè)。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是10元的整數(shù)倍）。今天一早，金明就開(kāi)始做預(yù)算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個(gè)主件的，下表就是一些主件與附件的例子：這樣，同一棵子樹(shù)構(gòu)成一個(gè)連續(xù)區(qū)間。如果每次都求一次塊的話，復(fù)雜度會(huì)很高。然而，我們所優(yōu)化后的程序依然有很高的時(shí)間復(fù)雜度，根本不能勝任此題。然后依次處理每一個(gè)元素：先取得所在區(qū)間的元素個(gè)數(shù)，再將該元素插入。對(duì)于每一個(gè)元素，統(tǒng)計(jì)一個(gè)區(qū)間中有多少元素比該元素大。其實(shí)我們這個(gè)題主要就是對(duì)于樹(shù)形結(jié)構(gòu)和線形結(jié)構(gòu)的選擇，所以我們對(duì)比算法4和算法1:不難發(fā)現(xiàn)，相比算法4，算法1其實(shí)多出的操作就是枚舉分配給左兒子多少錢。關(guān)鍵字：主件