Posted on 2011-03-19 22:38
Mato_No1 閱讀(931)
評論(0) 編輯 收藏 引用 所屬分類:
樹狀數(shù)組 、
AHOI
依照CLJ神犇的指示，最近本沙茶決定開始被數(shù)據(jù)結(jié)構(gòu)題虐……先找來了省內(nèi)的一道題（就是這道囧）……
題目大意：求兩個長度為5N的序列的最長公共子序列長度，在兩個序列中，整數(shù)1~N分別都出現(xiàn)5次。1<=N<=20000。
【注：本沙茶一開始用線段樹的，后來在看了CLJ神犇的標(biāo)程（Orz！！）之后終于明白了樹狀數(shù)組解法囧……】
LCS問題的樸素時間復(fù)雜度為O(NM)。對于本題顯然需要優(yōu)化。
觀察LCS的轉(zhuǎn)移方程：
F[i][j] = F[i-1][j-1]+1（當(dāng)A[i]==B[j]時）
F[i][j] = max{F[i-1][j], F[i][j-1]}（當(dāng)A[i]!=B[j]時）
可以將F用滾動數(shù)組來表示，即設(shè)F'為上階段的F（即F[i-1]），則本階段的F（即F[i]）可以由F'求得：
F[j] = F'[j-1]+1（當(dāng)A[i]==B[j]時）
F[j] = max{F'[j], F[j-1]}（當(dāng)A[i]!=B[j]時）
進一步，這個F'其實都不用記錄，只需在每一階段更新一遍F即可：
F[j] = F[j-1]+1（當(dāng)A[i]==B[j]時）
F[j] = max{F[j], F[j-1]}（當(dāng)A[i]!=B[j]時）
不過需要逆序更新（保證F[j-1]是上一階段的而不是本階段的），這與01背包有點像。
由題意可以發(fā)現(xiàn)，A[i]==B[j]的出現(xiàn)次數(shù)極少，在每階段中只會出現(xiàn)5次！我們可以預(yù)先求出這5個地方的值，然后對于其它的F[j]，其在本階段的值其實就是它前面的最大值（max{F[1..j-1]}），又因為我們最后只需知道F[N']（N'=5N，即序列長度）即可，故可設(shè)計出以下算法：
一開始F[1..N]均為0，然后將以下內(nèi)容執(zhí)行N'次，第i次：
（1）求出B序列中與A[i]相等的5個元素的位置，設(shè)為S[1..5]；
（2）依次更新F[S[5..1]]，每個都更新為它前面的最大值加1（很容易知道為神馬），其它的值暫時不管；
N'次執(zhí)行完后，整個序列中的最大值就是F[N']的值。由于這個算法中出現(xiàn)的主要操作是改動一個指定位置元素的值和找一個前綴區(qū)間中的最大值，因此可以采用樹狀數(shù)組，時間復(fù)雜度O(NlogN）（線段樹必TLE）。
【總結(jié)：在本題中使用了一種“推遲更新”的方法，即需要更新一個值時，先暫時不理它，等到需要引用到它的時候再更新。這種方法最常見的應(yīng)用就是線段樹的結(jié)點標(biāo)記。不過要注意的是，如果該值的推遲更新會對它后面要更新的值帶來問題（也就是，這些后更新的值需要引用該值的新值），就不能使用這種方法。在本題中，其它位置的值的改變只與這5個特殊的位置有關(guān)，與其它因素?zé)o關(guān)，故可以使用這種方法。】