|
留言
|
|
主題： |
考古問題疑似O(MN)解 |
|
留言人： |
LTH |
| 留言日期： | 2003/11/30 下午 12:51:25 |
| 留言IP： | |
| 留言內容： |
考古問題一般化即為Longest common increasing subsequence 故本文直接討論LCIS (本文為原創 如需轉錄請附註原作者(LTH)) 如有錯誤煩請指教XD 以下: 原先一直在想如何求LCS時順便LIS 可是後來發現這樣無論如何都會比LCS複雜度高:~ 想不出來的情況下 只好改變思路 "先 LIS 再 LCS " (即先對一個陣列n做LIS 每一步都去找m中哪些數和他們相同的) 現在令dp[i][j]代表n到i m到j為止之前最大的LCIS的長度 N,M分別為陣列n,m的長度 但dp[i][j]僅在n[i]==m[j]時有效 易見狀態轉移方程為: when n[i]==m[j] dp[i][j]= max(dp[k][x] when 1<=k<=i && 1<=x<=M && n[k]==m[x]) + 1 ----------------- 現在假設我們做到n[x],發現之前比它小的值共有n[a],n[b],n[c]三種 且他們分別是同值中index最大的 (最靠右的) /*n[a]==m[f],n[b]==m[e],n[c]==m[d]*/ n1 n2 n3...na...nb..nc...nx.......nN m1 m2 m3.....md.....me...mf....mM 由於dp陣列有向上包含性 不難發現 (1) 如果x1<=x2 y1<=y2 那 dp[x1][y1]<=dp[x2][y2] 所以如果在n[a]這些數左邊有和他們相同的數 那他們其實可以忽略不計 因為他們和n[a]在m中會找到相同的數 但是其搭配起來的dp值不會比n[a]的大 因此同值的只須考慮index最大的即可 這樣更可以發現 (2) 假設n[a]在m中找到的最大相同的index是e,n[b]找到的最大是d 那麼e必須大於d 否則n[a]不須考慮 (因為它會被n[b]包含) 還有 (3) 所有的n[a],n[b],n[c]必須在m中至少出現一次 否則也是不須做的 由以上(1) (3)兩個性質 我們可以看出每次LIS找之前的元素時 只有需要考慮比n[x]小且有在m中出現而在n中index又是同值最大的 這要如何達成呢? 不難 先預先把m的元素去除相異並sort (這只要做一次) 接著只需要把LIS做過的元素丟進一個map裡 以n[]的值做key,index做value (達成同值index最大) 然後每次都從map.begin()開始看看到比n[x]大為止 (確保比n[x]小) 同時增加一個counter從前往後對應掃m陣列 找相同的元素 (有點像Msort中的merge) (確保有在m中出現) 最後我們把找到的元素的index存入temp陣列中 由於這種事要做N次 所以這樣總共時間複雜度是O(NM) 那找到這些元素後要幹嘛呢? 現在仔細觀察性質(2) 可以發現性質(2)將會使得對每個n[p]==m[q]來說 它有需要考慮的以前的點連線後將會在平面上形成所謂的 "鋸齒形" (見圖) 設n[9]==m[6] *是所有的n和m相同的點 m1 m2 m3 m4 m5 m6 m7 m8 m9 m10 n1 n2 * * n3 * * n4 n5 * * * n6 * * n7 * * * n8 * n9 # # n10 套用(1)(2)(3)三個性質 則圖形將是 m1 m2 m3 m4 m5 m6 m7 m8 m9 m10 n1 | n2 | * * n3 (無關緊 | n4 要的點) | n5 | * n6 |-| n7 |-| * n8 --------| n9 # # n10 這讓你想到什麼了嗎? 沒錯! 就是最大0矩形(ACM 10043) 使用最大0矩形中的"堆疊法" 可以讓我們每次只要花O(點數)的時間就對整列的每個點找出他們個別的鋸齒 也就是他們個別有需要考慮哪些點 由於temp陣列中的元素是m的子集合又沒有重複 因此他們所有的和m中元素相同的點的數目相加絕不會超過M 所以 堆疊法將會在O(M)的時間內結束 至於當每個點找出他們的鋸齒後要如何找出最大的dp[][]值呢? 這其實只需要在堆疊法進行的途中 同時更新一個代表 "堆疊高度到多少時dp值最大是多少" 的陣列即可 這樣一來 每次找最大值將只需要O(1)的時間 由於這個步驟也需要做N次 所以總時間複雜度也是O(NM) 綜合前後兩個步驟 可知LCIS只需O(NM)的時間即可達成 也就是和LCS相同 除非LCS有更快的方法 不然此法應是最優的了 個人認為除了"先LIS再LCS"的思想外 最值得探討的是其突破了以往LCS的密集式dp的想法 (不論相不相同 每個點都做) 而採用"離散化dp"的思想 (只看相同的點 只考慮有需要的點) 以後應該有不少用處 :) 特別感謝人員: superpeter |
|
目前回應文章
|
| 回覆人 | 主題 | 回覆日期 |
| LTH | Re:考古問題疑似O(MN)解: | 2003/11/30 下午 12:53:28 |