夏令營(yíng)集訓(xùn)一中l(wèi)cis_第1頁(yè)
夏令營(yíng)集訓(xùn)一中l(wèi)cis_第2頁(yè)
夏令營(yíng)集訓(xùn)一中l(wèi)cis_第3頁(yè)
已閱讀5頁(yè)，還剩5頁(yè)未讀， 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、最長(zhǎng)公共上升子序列解題報(bào)告山東師大附中王呈瑞題目概括給定長(zhǎng)度均為N個(gè)序列A,B，求出他們的最大公共上升子序列：對(duì)于40%的數(shù)據(jù)，N=40對(duì)于100%的數(shù)據(jù)，N=2000兩個(gè)子問(wèn)題對(duì)于最大公共子序列，不難寫(xiě)出如下方程：fij = max(fi-1j, fij-1, fij + (ai=bj)時(shí)間復(fù)雜度為O(N2)而最大上升子序列為：fi = max(fj) + 1, aj ai可以用單調(diào)隊(duì)列優(yōu)化到O(NlogN)最先想到的式子所以將這兩個(gè)式子結(jié)合起來(lái)，方程式如下：fij = max(fij) + (ai = bj)條件為ii and jj and ai=bj and ai ai這樣復(fù)雜度為O(N

2、4)，可以過(guò)掉40%的數(shù)據(jù)。對(duì)于100%的數(shù)據(jù)，N=2000，貌似需要想出O(N2)的算法來(lái)。有些狀態(tài)是不需要的不難發(fā)現(xiàn)，當(dāng)ai!=bj時(shí)，fij這個(gè)狀態(tài)是不需要的，所以將所有需要的狀態(tài)離散化出來(lái)。雖然復(fù)雜度上限依然為O(N4)，但是狀態(tài)數(shù)變小了，所以運(yùn)行起來(lái)會(huì)更快一些。有些狀態(tài)可以壓縮到一塊在DP的過(guò)程中，假設(shè)我們先枚舉i，在枚舉j那么，ii這個(gè)條件是無(wú)需判斷的，因?yàn)閕總是不斷變大，這個(gè)條件總是滿足。所以，對(duì)于所有存在的狀態(tài)fij，我們將其最大值保存到一個(gè)數(shù)組f2j中，這樣：在枚舉j時(shí)，fij = max(f2i) + 1, ai ai然后將所得的結(jié)果，更新到f2中。這樣轉(zhuǎn)移的復(fù)雜度就變成了O(N)。轉(zhuǎn)移優(yōu)化在枚舉j的過(guò)程中，max(f2i)總是不斷變大的每一個(gè)fij不需要重新求出max(f2i)，只需要將該值記錄到max里，枚舉的過(guò)程中，不斷更新max，這樣轉(zhuǎn)移就變成了O(1)的了。綜上，總的時(shí)間復(fù)雜度上界為O(N2)。解法二

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論