網(wǎng)上找一些-試題解題報(bào)告

隱含的碼【關(guān)鍵字】最小覆蓋序列、動(dòng)態(tài)規(guī)【本文從模型的簡(jiǎn)化入手詳細(xì)闡述了本題的思考過程和算法，【正文IOI1000000題目關(guān)鍵是抓住重點(diǎn)理順關(guān)系簡(jiǎn)化模型下面就先對(duì)本題的模型進(jìn)行化。1規(guī)模依然大得驚人，需要進(jìn)一步簡(jiǎn)化。所以希望盡可能的縮短覆蓋序列的長(zhǎng)度，最好每個(gè)覆蓋序列不止是“右側(cè)最與其他覆蓋序列“它的長(zhǎng)度也不會(huì)超過1000，而它的所字長(zhǎng)度仍與原來(lái)一樣同樣是一個(gè)最優(yōu)解因此完全可以拋棄所有不“最小覆蓋序列”10000，所以“最小覆蓋序10000。這個(gè)規(guī)模已經(jīng)在可承受范圍之內(nèi)了。2、“最小覆蓋序列集”的建立和，本題的文本文件容量大應(yīng)該盡可能地減少讀入次數(shù)最好是只讀一就得到所“最小覆蓋序列考慮到覆蓋序列長(zhǎng)度不超過1000可以開1000，。這種算法在情況下所耗費(fèi)的時(shí)間是1000000*100*1000，顯然不行。它的缺整個(gè)碼字，浪費(fèi)太多來(lái)看另一種算法，它的基本思想是利用存在覆蓋序列側(cè)最小，如果能在緩沖區(qū)內(nèi)找到整個(gè)碼字，那么就把這個(gè)覆蓋序列“最小。Buffer:Array[1..MaxLength]OfChar;{文本緩沖區(qū)}Pos:Array[1..MaxN]OfByte;{碼字匹配指針}Sray[1..MaxN]OfLongInt;{覆蓋序列起始位置表}Cur:LongInt;{PosIfp>MaxLengthThenp:=1Fori:=1toNDoIfiPos[i]ThenIfPos[i]=1ThenStart[i]:=Cur;IfThenIf能在緩沖區(qū)內(nèi)找到整個(gè)碼字把這個(gè)覆蓋序列“最小覆蓋序列”表中;PosStartUntilEoln(Fin);單從程序循環(huán)結(jié)構(gòu)上看這種算法情況下所耗費(fèi)時(shí)間也是1000000*100*1000000*100*k，k<<1000。實(shí)際的測(cè)試證明了這種算法效率遠(yuǎn)碼字查詢得到因此不需要保存其它信息了綜上所述，對(duì)于每“最小覆蓋序列”最終只要保存三個(gè)信息就足夠了。所需空間一共是。這道題要求的是碼字長(zhǎng)度總和最大，是一個(gè)最優(yōu)化問題嘗試著使用動(dòng)f(a)=1a。（N）就是所要求的最優(yōu)解（N=“最小覆蓋序列”總數(shù)。定義L[i]=第i個(gè)碼字

(](

a的序列