動(dòng)態(tài)規(guī)劃算法時(shí)間效率的優(yōu)化(編輯修改稿)
2025-03-22 22:34 本頁面
【文章內(nèi)容簡(jiǎn)介】 +1,p]+m[p+1,j]+t[i, j]+t[i, p] 我們可以構(gòu)造如下的合并方案： { (i… q) [ (q+1...p) (p+1… j) ] } 它的得分 F2=m[i, q]+m[q+1,p]+m[p+1,j]+t[i, j]+t[q+1,j] 由于 qp， 所以 t[i, p]≤t[p+1,j]t[q+1,j] 所以 F1F2， 這與合并第 i堆到第 j堆石子的最優(yōu)斷開位置 s[i, j]=p矛盾 情況 t[i, p]t[p+1,j] 與情況 1是對(duì)稱的 。 狀態(tài)轉(zhuǎn)移方程優(yōu)化為： m[i,j]=max{m[i+1,j], m[i,j1]}+t[i,j] ij 規(guī)劃的邊界條件是： m[i,i]=0 算法的時(shí)間復(fù)雜度 O(n2)。 Back 例三 、 LOSTCITY (NOI`2023) [問題描述 ] 現(xiàn)給出一張單詞表 、 特定的語法規(guī)則和一篇文章： 文章和單詞表中只含 26個(gè)小寫英文字母 a… z。 單詞表中的單詞只有名詞 ， 動(dòng)詞和輔詞這三種詞性 ， 且相同詞性的單詞互不相同 。 單詞的個(gè)數(shù)不超過 1000， 單詞的長(zhǎng)度均不超過 20。 語法規(guī)則可簡(jiǎn)述為：名詞短語：任意個(gè)輔詞前綴接上一個(gè)名詞；動(dòng)詞短語：任意個(gè)輔詞前綴接上一個(gè)動(dòng)詞；句子：以名詞短語開頭 ， 名詞短語與動(dòng)詞短語相間連接而成 。 文章的長(zhǎng)度不超過 5k。 且已知文章是由有限個(gè)句子組成的 ， 句子只包含有限個(gè)單詞 。 編程將這篇文章劃分成最少的句子 ， 在此前提之下 ， 要求劃分出的單詞數(shù)最少 。 我們分別用 v,u,a表示動(dòng)詞 ， 名詞和輔詞 ， 給出的文章用 L[1..M]表示 ， 則狀態(tài)表示描述為： F(v,i)：表示將 L的前 i個(gè)字符劃分為以動(dòng)詞結(jié)尾 （ 當(dāng) iM時(shí) ， 可帶任意個(gè)輔詞后綴 ） 的最優(yōu)分解方案下劃分的句子數(shù)與單詞數(shù)； F(u,i)：表示將 L的前 i個(gè)字符劃分為以名詞結(jié)尾 （ 當(dāng) iM時(shí) ， 可帶任意個(gè)輔詞后綴 ） 的最優(yōu)分解方案下劃分的句子數(shù)與單詞數(shù) 。 狀態(tài)轉(zhuǎn)移方程為： F(v,i)=min{ F(u,j)+(0,1)， L(j+1..i)為動(dòng)詞； F(v,j)+(0,1)， L(j+1..i)為輔詞 ， iM； } F
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1