淺談數(shù)據(jù)的合理組織-文庫吧資料
2025-07-06 06:12本頁面
【正文】 詢問的復雜度為O(M2)，空間復雜度為O(M+N)。下面我們再來分析一個更經(jīng)典的題目：［例三］航線規(guī)劃【題意描述】給出一個有N個點M條邊的無向圖，兩點之間可能有多條邊，然后給出Q個命令，命令共有如下兩種：1 A B表示刪除一條A到B的邊2 A B表示詢問AB間共有多少條關鍵邊（即刪除改邊后使得AB不連通)數(shù)據(jù)保證任意時刻圖都是連通的。有興趣的同學可以參見何林同學2005年的論文。WC2005何林同學的論文中介紹了此題的另一解法，復雜度也為O(Nlog2(N))。按照從大到小的順序之前先對其區(qū)間進行統(tǒng)計，利用線段樹或樹狀數(shù)組。從大到小保證了現(xiàn)有的所有元素都比待插入的元素大。然后依次處理每一個元素：先取得所在區(qū)間的元素個數(shù)，再將該元素插入。統(tǒng)計區(qū)間元素個數(shù)我們可以直接利用線段樹和樹狀數(shù)組?！緮?shù)據(jù)組織方案二】我們從特殊情況考慮：假設我們在先根遍歷序中，需要統(tǒng)計元素k，并且k所在區(qū)間里的元素都比它大。這樣每統(tǒng)計一個元素的復雜度為O(log22(N))。然后在對每個分解區(qū)間進行處理：二分查找在該區(qū)間中有多少元素的權值比指定的元素的權值大。假設現(xiàn)在我們要統(tǒng)計一個區(qū)間(長度為L)。這樣，預處理可以用一個歸并排序，求得樹上所有區(qū)間的有序表。下面我們研究轉化后的問題：【數(shù)據(jù)組織方案一】我們不對數(shù)據(jù)進行更深入的組織，直接利用先根遍歷序，強制用數(shù)據(jù)結構來進行統(tǒng)計。對于每一個元素，統(tǒng)計一個區(qū)間中有多少元素比該元素大。元素相比較都指其權值大小相比較。我們給出一個例子：同一棵子樹構成一個連續(xù)的區(qū)間，這正方便了我們的統(tǒng)計。但是這些數(shù)據(jù)結構都是用于線型序列統(tǒng)計的，并且似乎沒有改造版本用于樹形結構。我們最大的困難在于求：其子樹中權值比該節(jié)點大的節(jié)點總數(shù)O(N2)的樸素統(tǒng)計方法是很容易想到的，但是本題的數(shù)據(jù)規(guī)模達到105，O(N2)的復雜度顯然太高。要求對于每一個節(jié)點，求：其中(1=N=105)【問題分析】對于要求的后面兩個值，我們很容易想到O(Nlog2(N))的算法：樹上除其子孫節(jié)點外比該節(jié)點大的節(jié)點總數(shù)：直接排序，在待統(tǒng)計節(jié)點前的與該節(jié)點權值不同的個數(shù)再減去問題1的答案即為所求。我們得到的啟示：憑第一感覺想出來的模型不一定是最好的，對于一個題目，我們充分挖掘其數(shù)據(jù)關系并加以利用，合理地組織數(shù)據(jù)并且嘗試用已有的知識來解決，推陳出新，才能不斷地進步。也就是說：樹的形態(tài)決定了在狀態(tài)轉移的時候要進行額外的枚舉。其實我們這個題主要就是對于樹形結構和線形結構的選擇，所以我們對比算法4和算法1:不難發(fā)現(xiàn)，相比算法4，算法1其實多出的操作就是枚舉分配給左兒子多少錢。反思這一題的幾個不同難度的版本，不難發(fā)現(xiàn)我們最終都用線形模型上的動態(tài)規(guī)劃取代了容易想到的樹形動態(tài)規(guī)劃算法。并且，這個算法模型對于以前有很多類似的樹形動態(tài)規(guī)劃題目都適用，這是我們在分析本題的過程中的意外收獲?，F(xiàn)在我們來設計動態(tài)規(guī)劃算法：定義：cost[i]表示第i個物品的價格weight[i]表示第i個物品的權值F[i][j]表示從第i個物品到第n個物品，最多花費j元，能得到的最大權值和。【算法4】根據(jù)前面的思考，我們先依次求出每棵樹的先根遍歷序，并保存在同一個序列l(wèi)ist[]中。這一結論似乎很顯然，但是我們并不是要在樹結構中用這一結論。思考并總結上面的結論：對于一個主件，我們?nèi)绻毁徺I的話，那么其附件我們都不用考慮，而直接“跳”到下一個主件。如果i是附件，那么實際上在到達下一個主件以前，i后面的附件是都不會被購買的。關鍵字：主件在前 序列 動態(tài)規(guī)劃我們聯(lián)想到利用樹的先根遍歷序，而且正好滿足上面的關系?，F(xiàn)在的題目是不是也可以類似解決呢？【組織數(shù)據(jù)方案四】算法3相對來說比較算法2更加一般，所以現(xiàn)在我們再回過頭來研究一下算法3，希望在分析過程中找到一些靈感。而利用了題目特殊條件的算法2和算法3，直接套用算法肯定是行不通的。N60M3200【問題分析】現(xiàn)在題目在原題的基礎上不僅放寬了附件的個數(shù)，還放寬了附件的層數(shù)，如圖所示：從上圖中，我們可以對本題有一個感性的認識：關系又“寬”又“深”。每個物品都有一個權值(50000)。分情況進行狀態(tài)轉移：情況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)轉移代價：O(1)時間復雜度同樣是O(NM)。原本樹上的問題經(jīng)過我們“合理地組織數(shù)據(jù)以后”，成功地轉化成了一個序列上的問題。如下圖：這樣做的好處是：一個附件能被購買的必要條件就是在其前面的最近的主件被購買了。但是對于利用原題條件特殊性的算法2，一個對象的取值可能達到N的組合級別，所以我們大可放棄對于算法2的討論。自然，我們當然嘗試用原題中的算法來套本題。任務 購買一些物品，總價格不超過M，使得被購買的物品的權值之和最大。郁悶的金明【題意描述】給出N個物品，可以直接被購買的稱為主件，而不能直接被購買的稱為附
高考資料相關推薦
鄂ICP備17016276號-1