國(guó)家集訓(xùn)隊(duì)論文 淺談數(shù)據(jù)的合理組織

1、四川省綿陽(yáng)南山中學(xué)何森淺談數(shù)據(jù)的合理組織引子題目越來(lái)越難數(shù)據(jù)關(guān)系越來(lái)越復(fù)雜！對(duì)組織數(shù)據(jù)的要求越來(lái)越高！合理組織在解題中越來(lái)越重要！【題意描述】給出N個(gè)物品，每個(gè)物品都有一個(gè)權(quán)值(50000)和一個(gè)價(jià)格(10000)。我們稱可以直接被購(gòu)置的物品為主件，稱不能被直接購(gòu)置的物品為附件，附件只有當(dāng)其主件被購(gòu)置了才能被購(gòu)置，一個(gè)主件最多有兩個(gè)附件，附件沒(méi)有下一級(jí)附件?！救蝿?wù)】用不超過(guò)M元錢(qián)，購(gòu)置一些物品，使得被購(gòu)置的物品的總權(quán)值最大。金明的預(yù)算方案【數(shù)據(jù)規(guī)?！縉60 M3200題目中給出的主件與附件間形成樹(shù)形結(jié)構(gòu)，而所有的物品間形成森林結(jié)構(gòu)。為了方便起見(jiàn)，我們給所有的主件都加上一個(gè)“上級(jí)主件，這樣，所有

2、的物品形成了一棵樹(shù)。數(shù)據(jù)的初步組織樹(shù)形動(dòng)態(tài)規(guī)劃算法!算法1狀態(tài)Fij表示給以i為根的子樹(shù)，總共花費(fèi)不超過(guò)j元，所能取得的最大權(quán)值和。?枚舉量太大，效率不高！總花費(fèi)不超過(guò)j用左兒子右兄弟表示法來(lái)表示這一棵樹(shù)！時(shí)間復(fù)雜度為 O(NM2)狀態(tài)總數(shù) O(MN)狀態(tài)轉(zhuǎn)移代價(jià) O(M)N*M*M=6*108，不太理想。狀態(tài)Fij表示以i為根的子樹(shù)總共花費(fèi)j元能獲得的最大權(quán)值和。我們只需要枚舉給左子樹(shù)分配多少錢(qián)，剩下的錢(qián)都分給右子樹(shù)。我們把配套的主件和附件看成一組。這樣，顯然對(duì)于每一組，可能的購(gòu)置方案最多只有如下五種：我們換一種數(shù)據(jù)組織方式1.附件沒(méi)有附件。2.每個(gè)主件最多只有兩個(gè)附件?？紤]此題特殊條件：1

3、.什么都不買(mǎi)2.只購(gòu)置主件3.購(gòu)置主件和附件14.購(gòu)置主件和附件25.全購(gòu)置類似經(jīng)典的-背包問(wèn)題！組織數(shù)據(jù)后，我們可以得到復(fù)雜度為O(NM)的優(yōu)秀算法 狀態(tài)總數(shù) O(MN) 狀態(tài)轉(zhuǎn)移代價(jià) O(1)郁悶的金明【題意描述】給出N個(gè)物品，每個(gè)物品都有一個(gè)權(quán)值(50000)和一個(gè)價(jià)格(10000)。我們稱可以直接被購(gòu)置的物品為主件，稱不能被直接購(gòu)置的物品為附件，附件只有當(dāng)其主件被購(gòu)置了才能被購(gòu)置，主件可以有任意多附件，附件沒(méi)有下一級(jí)附件?！救蝿?wù)】用不超過(guò)M元錢(qián)，購(gòu)置一些物品，使得被購(gòu)置的物品的總權(quán)值最大?！緮?shù)據(jù)規(guī)?！縉60 M3200題目放寬了“一個(gè)主件最多可以有兩個(gè)附件這個(gè)限制。問(wèn)題分析數(shù)據(jù)組織方式

4、依然適用效率以物品為節(jié)點(diǎn)的樹(shù)形結(jié)構(gòu)以組為元素的序列-我們需要重新組織數(shù)據(jù)！我們回想上題的數(shù)據(jù)組織方式。重新安排這些物品的順序，使得每個(gè)附件都緊跟其主件，保證其前面的最近的主件就是它附屬的主件。如以下圖：數(shù)據(jù)組織方案二主件1附件主件2附件附件主件3附件附件附件附件樹(shù)序列狀態(tài)Fijk表示從第i個(gè)物品到第n個(gè)物品，最多花費(fèi)j元，k表示i物品前面的主件有沒(méi)有被購(gòu)置，的最大價(jià)值和。這樣組織數(shù)據(jù)以后，一個(gè)附件能被購(gòu)置的必要條件是“其前面的最近的主件被購(gòu)置了。算法3主件1附件主件2附件附件主件3附件附件附件附件K=0 主件2沒(méi)有被購(gòu)置K=1 主件2有被購(gòu)置 狀態(tài)總數(shù) O(NM*2) 狀態(tài)轉(zhuǎn)移代價(jià)O(1) 時(shí)

5、間復(fù)雜度 O(NM)算法3重新組織數(shù)據(jù)后，我們?cè)俅纬晒Φ卦O(shè)計(jì)出了O(NM)的算法?！绢}意描述】給出N個(gè)物品，每個(gè)物品都有一個(gè)權(quán)值(50000)和一個(gè)價(jià)格(10000)。我們稱可以直接被購(gòu)置的物品為主件，稱不能被直接購(gòu)置的物品為附件，附件只有當(dāng)其主件被購(gòu)置了才能被購(gòu)置，主件可以有任意多附件，可以有多級(jí)附件。很郁悶的金明【任務(wù)】用不超過(guò)M元錢(qián)，購(gòu)置一些物品，使得被購(gòu)置的物品的總權(quán)值最大?！緮?shù)據(jù)規(guī)?！縉60 M3200現(xiàn)在的題目在原題的根底條件上不僅增加附件的個(gè)數(shù)，還出現(xiàn)了多級(jí)附件。問(wèn)題分析這是很一般的樹(shù)！一般的樹(shù)形結(jié)構(gòu)，我們還能不能用前面的數(shù)據(jù)組織方式呢？數(shù)據(jù)組織方式依然適用效率以物品為節(jié)點(diǎn)的樹(shù)形

6、結(jié)構(gòu)以組為元素的序列附件緊跟其主件的序列說(shuō)明這些數(shù)據(jù)組織方式都不合理，需要再次重新組織數(shù)據(jù)！現(xiàn)在我們?cè)倩剡^(guò)頭來(lái)研究一下前面一種數(shù)據(jù)組織方式：把同在一個(gè)組的主件放在附件的前面，將樹(shù)形問(wèn)題轉(zhuǎn)化到序列上來(lái)。而現(xiàn)在的問(wèn)題是：樹(shù)的高度增加了。組織數(shù)據(jù)方案三考慮：樹(shù)的先根遍歷序。仔細(xì)思考算法3的狀態(tài)轉(zhuǎn)移：主件1附件主件2附件附件主件3附件附件附件附件K=0遷移到此題中，對(duì)于一棵子樹(shù)，如果我們不購(gòu)置其根結(jié)點(diǎn)，那么其子孫都不必討論了因?yàn)槠渥訉O節(jié)點(diǎn)都不能被購(gòu)置但是我們不能用加一維的方法來(lái)記錄每個(gè)附件的主件是否被購(gòu)置了！這一結(jié)論似乎很顯然，但是我們并不是要在樹(shù)形結(jié)構(gòu)中運(yùn)用這一結(jié)論。正如上面提到的，我們要在樹(shù)的先根

7、遍序上進(jìn)行動(dòng)態(tài)規(guī)劃，而這一結(jié)論正是我們成功的關(guān)鍵。 狀態(tài)Fij表示在遍歷序列中從第i個(gè)物品到第n個(gè)物品，最多花費(fèi)j元，能得到的最大權(quán)值和。算法4主件1附件主件2附件附件主件3附件附件附件附件沒(méi)有購(gòu)置根結(jié)點(diǎn)！直接“跳過(guò)去！狀態(tài)總數(shù) O(NM)狀態(tài)轉(zhuǎn)移代價(jià)O(1)時(shí)間復(fù)雜度 O(NM)重新組織數(shù)據(jù)后，我們?cè)僖淮蝺?yōu)解此題。算法4這樣，實(shí)際上我們避開(kāi)了“記錄主件狀態(tài)的問(wèn)題！成功地實(shí)現(xiàn)了狀態(tài)的合法轉(zhuǎn)移小結(jié)樹(shù)形結(jié)構(gòu)樹(shù)形動(dòng)態(tài)規(guī)劃O(NM2)線形結(jié)構(gòu)合理地組織數(shù)據(jù)線形動(dòng)態(tài)規(guī)劃O(NM)【題意描述】給出一棵有N個(gè)節(jié)點(diǎn)的有根樹(shù)根為1號(hào)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有權(quán)值。要求對(duì)于每一個(gè)節(jié)點(diǎn)，求：1.其子樹(shù)中權(quán)值比該節(jié)點(diǎn)大的節(jié)點(diǎn)總

8、數(shù)2.樹(shù)上所有比該節(jié)點(diǎn)大的節(jié)點(diǎn)總數(shù)3.從根節(jié)點(diǎn)到該節(jié)點(diǎn)路徑中比該節(jié)點(diǎn)大的節(jié)點(diǎn)總數(shù)其中(1=N=105) 樹(shù)的果實(shí)問(wèn)題分析樹(shù)形上的統(tǒng)計(jì)問(wèn)題！序列上的統(tǒng)計(jì)問(wèn)題。對(duì)數(shù)據(jù)的初步組織我們進(jìn)行新的組織數(shù)據(jù)的嘗試：利用先根遍歷序?qū)?shù)轉(zhuǎn)化為序列，因?yàn)檫@樣，同一棵子樹(shù)構(gòu)成一個(gè)連續(xù)的區(qū)間，這是一個(gè)非常好的性質(zhì)。問(wèn)題轉(zhuǎn)化為：在一個(gè)由整數(shù)構(gòu)成的序列上，進(jìn)行N次區(qū)間詢問(wèn)。詢問(wèn)一個(gè)區(qū)間中有多少元素的權(quán)值比給定的值大。在組織后的數(shù)據(jù)中嘗試求解我們直接在組織成序列的數(shù)據(jù)中進(jìn)行統(tǒng)計(jì)。可以利用以有序表為元素的線段樹(shù)！每次統(tǒng)計(jì)的時(shí)間復(fù)雜度為O(log22(N) 總的時(shí)間復(fù)雜度為O(Nlog22(N) 預(yù)處理歸并排序O(Nlog2(N)我們重新考慮轉(zhuǎn)化后的問(wèn)題。進(jìn)一步組織數(shù)據(jù)答案即是區(qū)間中的元素個(gè)數(shù)！這是線段樹(shù)和樹(shù)狀數(shù)組的看家本領(lǐng)!考慮一種特殊的情況：當(dāng)前的序列中所有元素的權(quán)值均大于給定的值。一個(gè)很巧妙的方法：從大到小地向線段樹(shù)里面依次參加元素，邊加邊統(tǒng)計(jì)。324517667665431132451766排序依次插入并統(tǒng)計(jì)32451766這樣，我們的總時(shí)間復(fù)雜度為O(Nlog2(N