淺談數(shù)據(jù)的合理組織(存儲版)
【正文】 格（都是10元的整數(shù)倍）。 q ?。ㄆ渲衯表示該物品的價格（v10000），p表示該物品的重要度（1~5），q表示該物品是主件還是附件。他們以此來選擇最終要被咬掉的果子是哪一個。探險航線是雙向的，例如從1號星球到3號星球開辟探險航線，那么從3號星球到1號星球也可以使用這條航線。現(xiàn)在請你幫助完成。注意：我們保證無論航線如何被破壞，任意時刻任意兩個星球都能夠相互到達(dá)。被破壞的航線數(shù)目與詢問的次數(shù)總和不超過40000。此時，1號與5號星球之間的關(guān)鍵航線就有3條：13，34，45。星際空間站的Samuel II巨型計算機經(jīng)過長期探測，已經(jīng)鎖定了Samuel星系中許多星球的空間坐標(biāo)，并對這些星球從1開始編號3……。Nileh和Nixed就會各自選一個部分吃啦！比如對于左邊這棵樹，如果他們咬掉藍(lán)色的果子，那么就被分為紅色和黃色的兩個部分。） 從第2行到第m+1行，第j行給出了編號為j1的物品的基本數(shù)據(jù)，每行有3個非負(fù)整數(shù) v金明想買的東西很多，肯定會超過媽媽限定的N元。書柜【附錄】金明的預(yù)算方案 NOIP2006【題目描述】金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專用的很寬敞的房間。無處不體現(xiàn)出“對數(shù)據(jù)的合理組織”。即把一棵子樹的所有節(jié)點的Detph都減去同一個數(shù)。換句話說，就是把一些點的位置抬高，并把它們合并成一個塊。而對于每一個詢問我們都可以O(shè)(1)完成回答?！境醪浇M織數(shù)據(jù)】由前面的思考，我們把圖中的重連分量都“縮”成一個點。而橋的數(shù)量是O(N)級別的。WC2005何林同學(xué)的論文中介紹了此題的另一解法，復(fù)雜度也為O(Nlog2(N))。統(tǒng)計區(qū)間元素個數(shù)我們可以直接利用線段樹和樹狀數(shù)組。假設(shè)現(xiàn)在我們要統(tǒng)計一個區(qū)間(長度為L)。元素相比較都指其權(quán)值大小相比較。要求對于每一個節(jié)點，求：其中(1=N=105)【問題分析】對于要求的后面兩個值，我們很容易想到O(Nlog2(N))的算法：樹上除其子孫節(jié)點外比該節(jié)點大的節(jié)點總數(shù)：直接排序，在待統(tǒng)計節(jié)點前的與該節(jié)點權(quán)值不同的個數(shù)再減去問題1的答案即為所求。反思這一題的幾個不同難度的版本，不難發(fā)現(xiàn)我們最終都用線形模型上的動態(tài)規(guī)劃取代了容易想到的樹形動態(tài)規(guī)劃算法。這一結(jié)論似乎很顯然，但是我們并不是要在樹結(jié)構(gòu)中用這一結(jié)論?，F(xiàn)在的題目是不是也可以類似解決呢？【組織數(shù)據(jù)方案四】算法3相對來說比較算法2更加一般，所以現(xiàn)在我們再回過頭來研究一下算法3，希望在分析過程中找到一些靈感。分情況進(jìn)行狀態(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)時間復(fù)雜度同樣是O(NM)。自然，我們當(dāng)然嘗試用原題中的算法來套本題。weight[i][k]表示分組后第i個對象的第k種購買方案的總權(quán)值。【數(shù)據(jù)組織方案二】上面我們把本題同01背包進(jìn)行了類比。但是題目與背包卻有一些差別：附件不能被直接購買。事實上，這兩個方面在實際運用中往往不是獨立的，通常需要聯(lián)合運用。對數(shù)據(jù)進(jìn)行合理地組織，正是我們面對上述題目時的一種有效手段。目的在于引起讀者對于數(shù)據(jù)的合理組織的關(guān)注，并在今后的解題中能積極并靈活地運用這一手段。對數(shù)據(jù)組織的合理化，不僅在我們設(shè)計算法時能起到優(yōu)化程序效率的作用，有時，我們在建立解題模型時，合理地組織數(shù)據(jù)可能給我們提供新的思考角度，從而優(yōu)化解題模型，例一就是這樣的一個例子。【數(shù)據(jù)組織方案一】假設(shè)我們忽略數(shù)據(jù)的特殊性，單從樹結(jié)構(gòu)考慮，我們?nèi)菀紫氲降囊粋€算法是：給所有主件加上一個“級超主件”，把原來的所有主件都變成“超級主件”的附件，如下圖： (圖2)【算法一】這樣，在這棵樹上，我們可以設(shè)計一個動態(tài)規(guī)劃算法： 定義：cost[a]表示a節(jié)點所代表的物品的價格score[a]表示a節(jié)點所代表的物品的得分狀態(tài)f[a][b]表示以節(jié)點a為根的子樹，總共花費不超過b元的最多得分。我們回到題目并考慮其特殊性：。其中1=k=5且cost[i][k]=j 狀態(tài)總數(shù)：O(NM)轉(zhuǎn)移代價：O(1)這樣，我們得到了一個時間復(fù)雜度為O(NM)的優(yōu)秀算法。我們是否有合理的組織數(shù)據(jù)的辦法呢？【數(shù)據(jù)組織方案三】重新安排這些物品的順序，使得每個附件都緊跟其主件，保證其左邊的第一個主件就是它附屬的主件。任務(wù) 購買一些物品，總價格不超過M，使得被購買的物品的權(quán)值之和最大。但是這樣有什么好處嗎？還能進(jìn)行動態(tài)規(guī)劃嗎？怎樣設(shè)計狀態(tài)才能傳遞父節(jié)點的狀態(tài)呢？我們再回過去看算法3的狀態(tài)轉(zhuǎn)移：假設(shè)當(dāng)前狀態(tài)是F[i][j][k]，且k=0。為了利用上面的結(jié)論，我們還要求出以節(jié)點i為根的子樹的節(jié)點總數(shù)count[i]。而在線形的序列上，沒有用的錢自然地被分配給后面的元素。我們自然想到利用線段樹、樹狀數(shù)組這些優(yōu)秀的統(tǒng)計數(shù)據(jù)結(jié)構(gòu)來進(jìn)行題目中要求的統(tǒng)計任務(wù)。這正是我們比較熟悉的序列上的統(tǒng)計問題。然后把
高考資料相關(guān)推薦
鄂ICP備17016276號-1