浙江大學(xué)_acm程序設(shè)計(jì)競(jìng)賽_動(dòng)態(tài)規(guī)劃講義-文庫(kù)吧
2024-12-23 22:44 本頁(yè)面
【正文】 到 3 1的最優(yōu)值 . 買車票 ?買車票 (Ural1031) Ekaterinburg城到 Sverdlovsk城有直線形的鐵路線。 兩城之間還有其他一些?？空?,總站數(shù)為 N。 各站按照離 Ekaterinburg城的距離編號(hào)。 Ekaterinburg城編號(hào)為 1，Sverdlovsk城編號(hào)為 N。 買車票 某兩站之間車票價(jià)格由這兩站的距離 X決定 . 當(dāng) 0X=L1時(shí)，票價(jià)為 C1元 . 當(dāng) L1X=L2時(shí)，票價(jià)為 C2元 . 當(dāng) L2X=L3時(shí)，票價(jià)為 C3元 . 當(dāng)兩站距離大于 L3時(shí)沒有直達(dá)票，所以有時(shí)候要買幾 次票做幾次車才行。 比如，在上面的例圖中， 26沒有直達(dá)票，有幾種買票 方法可以從 26，其中一種是買 C2元的 23車票，再買 C3元的 36車票。 買車票 給定起點(diǎn)站和終點(diǎn)站還有 L1,L2,L3,C1,C2,C3，求出要從 起點(diǎn)到終點(diǎn)最少要花多少錢 . 怎么辦 買車票 當(dāng)前所在的某個(gè)車站 這一題的以前狀態(tài)其實(shí)只有 3種 .即滿足 3種距離 (收費(fèi) )情況的 3個(gè)車站 .要知道這 3個(gè)車站可以先做一個(gè)預(yù)處理 .顯然這 3個(gè)車站在滿足距離限制的條件下應(yīng)該越遠(yuǎn)越好 . 買車票 ? 預(yù)處理 很容易想出一個(gè) N^2的預(yù)處理 ,但是那樣是會(huì)超時(shí)的 .由于盡量要讓車站離得遠(yuǎn) (費(fèi)用是一樣的啊 )因此在每種收費(fèi)情況下 ,每個(gè)車站的以前狀態(tài)車站一定是遞增的序列 .這里是只要 O(N)的程序 : for j:=1 to 3 do begin k:=en1。 for i:=en downto be do begin while (way[i]way[k]=l[j])and(k=be) do dec(k)。 p[i][j]:=k+1。 end。 end。 數(shù)組 P[i][j]表示的是 I狀態(tài)的第 j種以前狀態(tài) . 買車票 動(dòng)態(tài)規(guī)劃的部分 for i:=be+1 to en do {枚舉當(dāng)前狀態(tài) } begin cost[i]:=maxlongint。 for j:=1 to 3 do {枚舉以前狀態(tài) } begin if (p[i][j]i) and (cost[i] cost[p[i][j]] + c[j]) then cost[i]:=cost[p[i][j]]+c[j]。 end。 end。 動(dòng)規(guī)的要訣－狀態(tài) ?有時(shí)候當(dāng)前狀態(tài)確定后 ,以前狀態(tài)就已經(jīng)確定 ,則無(wú)需枚舉 . Tom的煩惱 ? Tom是一個(gè)非常有創(chuàng)業(yè)精神的人，由于大學(xué)學(xué)的是汽車制造專業(yè)，所以畢業(yè)后他用有限的資金開了一家汽車零件加工廠， 專門為汽車制造商制造零件。由于資金有限，他只能先購(gòu)買一臺(tái)加工機(jī)器?，F(xiàn)在他卻遇到了麻煩，多家汽車制造商需要他加 工一些不同零件（由于廠家和零件不同，所以給的加工費(fèi)也不同），而且不同廠家對(duì)于不同零件的加工時(shí)間要求不同（有些加工時(shí)間要求甚至是沖突的，但開始和結(jié)束時(shí)間相同不算沖突）。Tom當(dāng)然希望能把所有的零件都加工完，以得到更多的加工費(fèi)，但當(dāng)一些零件的加工時(shí)間要求有沖突時(shí)，在某個(gè)時(shí)間內(nèi)他只能選擇某種零件加工（因?yàn)樗挥幸慌_(tái)機(jī)器），為了賺得盡量多的加工費(fèi)，Tom不知如何進(jìn)行取舍。 Tom的煩惱 ? Tom的煩惱 按結(jié)束時(shí)間排序，枚舉結(jié)束時(shí)間作為當(dāng)前狀態(tài) ,以前狀態(tài)就是該結(jié)束時(shí)間對(duì)應(yīng)的起始時(shí)間，這是已經(jīng)確定的 . 文字游戲 ? 文字游戲 (fairfox邀請(qǐng)賽 1) 給你一份單詞表，和一個(gè)句子。求出該句子能有多少中不同的劃分方法 .例如 : 單詞是 ab cd a b c d 句子是 abcd 他共有 4種 完全 劃分方案 : ab/cd a/b/c/d a/b/cd ab/c/d。 當(dāng)前狀態(tài)就是單詞在句子中向后靠的位置 ,以前狀態(tài)就是確定這個(gè)單詞位置以后 ,除掉這個(gè)單詞長(zhǎng)度后的一個(gè)位置 .狀態(tài)轉(zhuǎn)移方程是 :F[i]:=F[i]+F[ilength(word[j])] IOI中有一題 《 前綴 》 也是類似的題目 . 決策中的定量 ?狀態(tài)轉(zhuǎn)移方程的構(gòu)造無(wú)疑是動(dòng)態(tài)規(guī)劃過程中最重要的一步 ,也是最難的一步 .對(duì)于大多數(shù)的動(dòng)態(tài)規(guī)劃 ,尋找狀態(tài)轉(zhuǎn)移方程有一條十分高效的通道 ,就是尋找變化中的不變量 .定量處理的過程也就是決策實(shí)施的過程 . 尋找定量 ?最佳加法表達(dá)式 ?有一個(gè)由 1..9組成的數(shù)字串 .問如果將 m個(gè)加號(hào)插入到這個(gè)數(shù)字串中 .使得所形成的算術(shù)表達(dá)式的值最小 . 或許你不明白我在說什么 ,那么我們通過題目來說明吧 最佳加法表達(dá)式 ? 這一題中的定量是什么呢 ?因?yàn)槭翘砣爰犹?hào) ,那么添完加號(hào)后 ,表達(dá)式的最后一定是個(gè)數(shù)字串 ,這就是定量 .從這里入手 ,不難發(fā)現(xiàn)可以把以前狀態(tài)認(rèn)為是在前 i個(gè)字符中插入 k1個(gè)加號(hào)(這里的 i是當(dāng)作決策在枚舉 ),然后 i+1到最后一位一定是整個(gè)沒有被分割的數(shù)字串 ,第 k個(gè)加號(hào)就添在 i與 i+1個(gè)數(shù)字之間 .這樣就構(gòu)造出了整個(gè)數(shù)字串的最優(yōu)解 .而至于前 i個(gè)字符中插入k1個(gè)加號(hào) ,這又回到了原問題的形式 ,也就是回到了以前狀態(tài) ,所以狀態(tài)轉(zhuǎn)移方程就能很快的構(gòu)造出來了 . 最佳加法表達(dá)式 ?用 f[i,j],表示的是在前 i個(gè)字符中插入 j個(gè)加號(hào)能達(dá)到的最小值
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1