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