淺談數(shù)據(jù)的合理組織

1、淺談數(shù)據(jù)的合理組織淺談數(shù)據(jù)的合理組織 引子引子 題目越來越難題目越來越難數(shù)據(jù)關(guān)系越來越復(fù)雜！數(shù)據(jù)關(guān)系越來越復(fù)雜！ 對組織數(shù)據(jù)的要求越來越高！對組織數(shù)據(jù)的要求越來越高！ 合理組織在解題中越來越重要！合理組織在解題中越來越重要！ 【題意描述題意描述】 給出N個(gè)物品，每個(gè)物品都有一個(gè)權(quán)值(50000)和一個(gè)價(jià)格 (10000)。我們稱可以直接被購買的物品為主件，稱不能被直 接購買的物品為附件，附件只有當(dāng)其主件被購買了才能被購買， 一個(gè)主件最多有兩個(gè)附件，附件沒有下一級附件。 【任務(wù)任務(wù)】 用不超過M元錢，購買一些物品，使得被購買的物品的總權(quán)值最 大。 金明的預(yù)算方案金明的預(yù)算方案 【數(shù)據(jù)規(guī)模數(shù)據(jù)規(guī)模

2、】 N60 M3200 題目中給出的主件與附件間形成樹形結(jié)構(gòu)，而所有的物品間形 成森林結(jié)構(gòu)。為了方便起見，我們給所有的主件都加上一個(gè)“ 上級主件”，這樣，所有的物品形成了一棵樹。 數(shù)據(jù)的初步數(shù)據(jù)的初步組織組織 樹形動態(tài)規(guī)劃算法樹形動態(tài)規(guī)劃算法! 算法算法1 狀態(tài)狀態(tài)FijFij表示給以表示給以i i為根的子樹，總共花費(fèi)不超過為根的子樹，總共花費(fèi)不超過j j元，元， 所能取得的最大權(quán)值和。所能取得的最大權(quán)值和。 ? ? ? 枚舉量太大，效率不高！枚舉量太大，效率不高！ 總花費(fèi)不超過總花費(fèi)不超過j 用用左兒子右兄弟表示法左兒子右兄弟表示法來表示這一棵樹！來表示這一棵樹！ 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為

3、O(NMO(NM2 2) ) 狀態(tài)總數(shù)狀態(tài)總數(shù) O(MN)O(MN) 狀態(tài)轉(zhuǎn)移代價(jià)狀態(tài)轉(zhuǎn)移代價(jià) O(M)O(M) N*M*M=6*108，不太理想。，不太理想。 狀態(tài)狀態(tài)FijFij表示以表示以i i為根的子樹總共花費(fèi)為根的子樹總共花費(fèi)j j元能獲得的最大權(quán)值和。元能獲得的最大權(quán)值和。 我們只需要枚舉給左子樹分配多少錢，剩下的錢都分給右子樹。我們只需要枚舉給左子樹分配多少錢，剩下的錢都分給右子樹。 我們把配套的主件和附件看成一組。 這樣，顯然對于每一組，可能的購買方案最多只有如下五種： 我們換一種數(shù)據(jù)組織方式我們換一種數(shù)據(jù)組織方式 1.附件沒有附件。附件沒有附件。 2.每個(gè)主件最多只有兩個(gè)附件

4、。每個(gè)主件最多只有兩個(gè)附件。 考慮本題特殊條件： 1.什么都不買什么都不買 2.只購買主件只購買主件 3.購買主件和附件購買主件和附件1 4.購買主件和附件購買主件和附件2 5.全購買全購買 類似經(jīng)典的類似經(jīng)典的-背包問題！背包問題！ 組織數(shù)據(jù)后，我們可以得到復(fù)雜度為組織數(shù)據(jù)后，我們可以得到復(fù)雜度為O(NM)O(NM)的優(yōu)秀算法的優(yōu)秀算法 狀態(tài)總數(shù)狀態(tài)總數(shù) O(MN) 狀態(tài)轉(zhuǎn)移代價(jià)狀態(tài)轉(zhuǎn)移代價(jià) O(1) 郁悶的金明郁悶的金明 【題意描述題意描述】 給出N個(gè)物品，每個(gè)物品都有一個(gè)權(quán)值(50000)和一個(gè)價(jià)格 (10000)。我們稱可以直接被購買的物品為主件，稱不能被直 接購買的物品為附件，附件只

5、有當(dāng)其主件被購買了才能被購買， 主件可以有任意多附件主件可以有任意多附件，附件沒有下一級附件。 【任務(wù)任務(wù)】 用不超過M元錢，購買一些物品，使得被購買的物品的總權(quán)值最 大。 【數(shù)據(jù)規(guī)模數(shù)據(jù)規(guī)模】 N60 M3200 題目放寬了“一個(gè)主件最多可以有兩個(gè)附件”這個(gè)限制。 問題分析問題分析 數(shù)據(jù)組織方式數(shù)據(jù)組織方式依然適用效率 以物品為節(jié)點(diǎn)的樹形結(jié)構(gòu) 以組為元素的序列- 我們回想上題的數(shù)據(jù)組織方式。 重新安排這些物品的順序，使得每個(gè)附件都緊跟其主件，保 證其前面的最近的主件就是它附屬的主件。如下圖： 數(shù)據(jù)組織方案二數(shù)據(jù)組織方案二 主件主件1附件附件主件主件2附件附件附件附件主件主件3附件附件附件附件

6、附件附件附件附件 樹樹序列序列 狀態(tài)狀態(tài)Fijk表示從第表示從第i個(gè)物品到第個(gè)物品到第n個(gè)物品，最多花費(fèi)個(gè)物品，最多花費(fèi)j元，元，k 表示表示i物品前面的主件有沒有被購買，的最大價(jià)值和。物品前面的主件有沒有被購買，的最大價(jià)值和。 這樣組織數(shù)據(jù)以后，一個(gè)附件能被購買的必要條件是這樣組織數(shù)據(jù)以后，一個(gè)附件能被購買的必要條件是“其前面的最其前面的最 近的主件被購買了近的主件被購買了”。 算法算法3 主件主件1附件附件主件主件2附件附件附件附件主件主件3附件附件附件附件附件附件附件附件 K=0 主件主件2沒有被購買沒有被購買K=1 主件主件2有被購買有被購買 狀態(tài)總數(shù)狀態(tài)總數(shù) O(NM*2) 狀態(tài)轉(zhuǎn)移

7、代價(jià)狀態(tài)轉(zhuǎn)移代價(jià)O(1) 時(shí)間復(fù)雜度時(shí)間復(fù)雜度 O(NM) 算法算法3 重新組織數(shù)據(jù)后，我們再次成功地設(shè)重新組織數(shù)據(jù)后，我們再次成功地設(shè) 計(jì)出了計(jì)出了O(NM)的算法。的算法。 【題意描述題意描述】 給出N個(gè)物品，每個(gè)物品都有一個(gè)權(quán)值(50000)和一個(gè)價(jià)格 (10000)。我們稱可以直接被購買的物品為主件，稱不能被直 接購買的物品為附件，附件只有當(dāng)其主件被購買了才能被購買， 主件可以有任意多附件，可以有多級附件。主件可以有任意多附件，可以有多級附件。 很郁悶的金明很郁悶的金明 【任務(wù)任務(wù)】 用不超過M元錢，購買一些物品，使得被購買的物品的總權(quán)值最 大。 【數(shù)據(jù)規(guī)模數(shù)據(jù)規(guī)模】 N60 M320

8、0 現(xiàn)在的題目在原題的基礎(chǔ)條件上不僅增加附件的個(gè)數(shù)，還出現(xiàn)現(xiàn)在的題目在原題的基礎(chǔ)條件上不僅增加附件的個(gè)數(shù)，還出現(xiàn) 了多級附件。了多級附件。 問題分析問題分析 這是很一般的樹！這是很一般的樹！ 一般的樹形結(jié)構(gòu)，我們還能不能用前面的數(shù)據(jù)組一般的樹形結(jié)構(gòu)，我們還能不能用前面的數(shù)據(jù)組 織方式呢？織方式呢？ 數(shù)據(jù)組織方式數(shù)據(jù)組織方式依然適用效率 以物品為節(jié)點(diǎn)的樹形結(jié)構(gòu) 以組為元素的序列 附件緊跟其主件的序列 說明這些數(shù)據(jù)組織方式都說明這些數(shù)據(jù)組織方式都不合理不合理，需要再次重新組織數(shù)據(jù)！，需要再次重新組織數(shù)據(jù)！ 現(xiàn)在我們再回過頭來研究一下前面一種數(shù)據(jù)組織方式： 把同在一個(gè)組的主件放在附件的前面，將樹形問

9、題轉(zhuǎn)化到序 列上來。 而現(xiàn)在的問題是：樹的高度增加了。樹的高度增加了。 組織數(shù)據(jù)方案三組織數(shù)據(jù)方案三 考慮：考慮：樹的先根遍歷序。樹的先根遍歷序。 仔細(xì)思考算法仔細(xì)思考算法3的狀態(tài)轉(zhuǎn)移：的狀態(tài)轉(zhuǎn)移： 主件主件1附件附件主件主件2附件附件附件附件主件主件3附件附件附件附件附件附件附件附件 K=0 遷移到本題中，對于一棵子樹，如果我們遷移到本題中，對于一棵子樹，如果我們 不購買其根結(jié)點(diǎn)，那么其子孫都不必討論不購買其根結(jié)點(diǎn)，那么其子孫都不必討論 了（因?yàn)槠渥訉O節(jié)點(diǎn)都不能被購買）了（因?yàn)槠渥訉O節(jié)點(diǎn)都不能被購買） 但是我們不能用加一維的方法來記錄每但是我們不能用加一維的方法來記錄每 個(gè)附件的主件是否被購

10、買了！個(gè)附件的主件是否被購買了！ 這一結(jié)論似乎很顯然，但是我們并不是要在樹形 結(jié)構(gòu)中運(yùn)用這一結(jié)論。 正如上面提到的，我們要在樹的先根遍序上進(jìn)行動動 態(tài)規(guī)劃態(tài)規(guī)劃，而這一結(jié)論正是我們成功的關(guān)鍵。 狀態(tài)Fij表示在遍歷序列遍歷序列中從第i個(gè)物品到第n個(gè)物品，最多 花費(fèi)j元，能得到的最大權(quán)值和。 算法算法4 主件主件1附件附件主件主件2附件附件附件附件主件主件3附件附件附件附件附件附件附件附件 沒有購買根結(jié)點(diǎn)！沒有購買根結(jié)點(diǎn)！ 直接直接“跳跳”過去！過去！ 狀態(tài)總數(shù)狀態(tài)總數(shù) O(NM) 狀態(tài)轉(zhuǎn)移代價(jià)狀態(tài)轉(zhuǎn)移代價(jià)O(1) 時(shí)間復(fù)雜度時(shí)間復(fù)雜度 O(NM) 重新組織數(shù)據(jù)后，我們再一次優(yōu)解此題。重新組織數(shù)

11、據(jù)后，我們再一次優(yōu)解此題。 算法算法4 這樣，實(shí)際上我們避開了這樣，實(shí)際上我們避開了“記錄主件狀態(tài)記錄主件狀態(tài)” 的問題！成功地實(shí)現(xiàn)了狀態(tài)的合法轉(zhuǎn)移的問題！成功地實(shí)現(xiàn)了狀態(tài)的合法轉(zhuǎn)移 小結(jié)小結(jié) 樹形結(jié)構(gòu)樹形結(jié)構(gòu)樹形動態(tài)規(guī)劃樹形動態(tài)規(guī)劃O(NM2) 線形結(jié)構(gòu)線形結(jié)構(gòu) 合理地組織數(shù)據(jù)合理地組織數(shù)據(jù) 線形動態(tài)規(guī)劃線形動態(tài)規(guī)劃O(NM) 【題意描述】 給出一棵有N個(gè)節(jié)點(diǎn)的有根樹（根為1號節(jié)點(diǎn)），每個(gè)節(jié)點(diǎn)有權(quán) 值。 要求對于每一個(gè)節(jié)點(diǎn)，求： 1.其子樹中權(quán)值比該節(jié)點(diǎn)大的節(jié)點(diǎn)總數(shù) 2.樹上所有比該節(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í) 問

12、題分析問題分析 樹形上的統(tǒng)計(jì)問題！樹形上的統(tǒng)計(jì)問題！ 序列上的統(tǒng)計(jì)問題。序列上的統(tǒng)計(jì)問題。 對數(shù)據(jù)的初步組織對數(shù)據(jù)的初步組織 我們進(jìn)行新的組織數(shù)據(jù)的嘗試我們進(jìn)行新的組織數(shù)據(jù)的嘗試：利用先根遍歷序?qū)滢D(zhuǎn)化：利用先根遍歷序?qū)滢D(zhuǎn)化 為序列，因?yàn)檫@樣，為序列，因?yàn)檫@樣，同一棵子樹構(gòu)成一個(gè)連續(xù)的區(qū)間同一棵子樹構(gòu)成一個(gè)連續(xù)的區(qū)間，這，這 是一個(gè)非常好的性質(zhì)。是一個(gè)非常好的性質(zhì)。 問題轉(zhuǎn)化為：問題轉(zhuǎn)化為：在一個(gè)由整數(shù)構(gòu)成的序列上，進(jìn)行在一個(gè)由整數(shù)構(gòu)成的序列上，進(jìn)行N次區(qū)間詢次區(qū)間詢 問。詢問一個(gè)區(qū)間中有多少元素的權(quán)值比給定的值大。問。詢問一個(gè)區(qū)間中有多少元素的權(quán)值比給定的值大。 在組織后的數(shù)據(jù)中嘗試求解在

13、組織后的數(shù)據(jù)中嘗試求解 我們直接在組織成序列的數(shù)據(jù)中進(jìn)行統(tǒng)計(jì)。可以利用以我們直接在組織成序列的數(shù)據(jù)中進(jìn)行統(tǒng)計(jì)。可以利用以 有序表為元素的線段樹！有序表為元素的線段樹！ 每次統(tǒng)計(jì)的時(shí)間復(fù)雜度為每次統(tǒng)計(jì)的時(shí)間復(fù)雜度為O(log22(N) 總的時(shí)間復(fù)雜度為總的時(shí)間復(fù)雜度為O(Nlog22(N) 預(yù)處理預(yù)處理歸并排序歸并排序O(Nlog2(N) 我們重新考慮轉(zhuǎn)化后的問題。 進(jìn)一步組織數(shù)據(jù)進(jìn)一步組織數(shù)據(jù) 答案即是區(qū)間中的元素個(gè)數(shù)！答案即是區(qū)間中的元素個(gè)數(shù)！ 這是線段樹和樹狀數(shù)組的看家本領(lǐng)這是線段樹和樹狀數(shù)組的看家本領(lǐng)! 考慮一種特殊的情況：考慮一種特殊的情況： 當(dāng)前的序列中所有元素的權(quán)值均大于給定的值。當(dāng)前的序列中所有元素的權(quán)值均大于給定的值。 一個(gè)很巧妙的方法：從大到小地向線段樹里面依次加入元從大到小地向線段樹里面依次加入元 素，邊加邊統(tǒng)計(jì)。素，邊加邊統(tǒng)計(jì)。 32451766 76654311 32451766 排序排序 依次插入并統(tǒng)計(jì)依次插入并統(tǒng)計(jì) 32451766 這樣，我們的總時(shí)間復(fù)雜度為這樣，我們的總時(shí)間復(fù)雜度為O(Nlog2(N) 小結(jié)小結(jié)