浙江大學(xué)_acm程序設(shè)計(jì)競(jìng)賽_動(dòng)態(tài)規(guī)劃講義-資料下載頁(yè)
2025-01-07 22:44本頁(yè)面
【正文】 輸出。這里 N=10000 網(wǎng)絡(luò) ? 枚舉每個(gè)點(diǎn)，然后 DFS復(fù)雜度 O(N2)，超時(shí)是顯然的事情。 ? 可以發(fā)現(xiàn)其實(shí)有很多 DFS都重復(fù)做了同樣的工作，產(chǎn)生了浪費(fèi)，所以應(yīng)該選擇動(dòng)態(tài)規(guī)劃解決這個(gè)問(wèn)題。 ? 樹(shù)上的動(dòng)規(guī)，是否直接可以寫(xiě)出下面的狀態(tài)轉(zhuǎn)移方城呢？ ? f[i]:=max(f[son],f[father])+1 ? 廢話(huà)，顯然是不行的， son和 father的值不可能同時(shí)得到。 ? 但是不要放棄，解決這個(gè)沖突的方法，就是采用二次動(dòng)規(guī)。 網(wǎng)絡(luò) ? 第一次動(dòng)規(guī)做 f[i]:=max(f[son])+1，第二次動(dòng)規(guī)做 f[i]:=max(f[i],f[father] + 1) 。 ? 但是存在一個(gè)問(wèn)題就是如果 f[father]的值是從 i那里得到的，這樣計(jì)算顯然就錯(cuò)了。 ? 不要放棄，在實(shí)際操作過(guò)程中， f需要記下兩個(gè)值，一個(gè)是最優(yōu)值，一個(gè)是次優(yōu)值，這兩個(gè)值必須由不用的子結(jié)點(diǎn)得到。這樣當(dāng)最優(yōu)值發(fā)生矛盾的時(shí)候，次優(yōu)值一定不會(huì)矛盾。問(wèn)題就解決了。復(fù)雜度 O(N)十分的理想。 總結(jié) ?動(dòng)態(tài)規(guī)劃有很多東西還需要我們更加努力地去探索和學(xué)習(xí) .總體上說(shuō)來(lái) ,動(dòng)態(tài)規(guī)劃是個(gè)既簡(jiǎn)單又不簡(jiǎn)單的算法 ,熟練地掌握了動(dòng)態(tài)規(guī)劃 ,也就熟練地控制了比賽 . That’s all! Thank you for listening. 動(dòng)規(guī)練習(xí)題 ? 垃圾陷阱（ USACOamp。TJU1087） ? 卡門(mén) —— 農(nóng)夫約翰極其珍視的一條Holsteins奶牛 —— 已經(jīng)落了到 “ 垃圾井 ” 中。 “ 垃圾井 ” 是農(nóng)夫們?nèi)永牡胤?，它的深度?D (2 = D = 100)英尺?？ㄩT(mén)想把垃圾堆起來(lái)，等到堆得與井同樣高時(shí)，她就能逃出井外了。另外，卡門(mén)可以通過(guò)吃一些垃圾來(lái)維持自己的生命。每個(gè)垃圾都可以用來(lái)吃或堆放，并且堆放垃圾不用花費(fèi)卡門(mén)的時(shí)間。假設(shè)卡門(mén)預(yù)先知道了每個(gè)垃圾扔下的時(shí)間 t(0 t = 1000)，以及每個(gè)垃圾堆放的高度 h(1 = h = 25)和吃進(jìn)該垃圾能維持生命的時(shí)間 f(1 = f = 30)，要求出卡門(mén)最早能逃出井外的時(shí)間，假設(shè)卡門(mén)當(dāng)前體內(nèi)有足夠持續(xù)10小時(shí)的能量，如果卡門(mén) 10小時(shí)內(nèi)沒(méi)有進(jìn)食，卡門(mén)就將餓死。 動(dòng)規(guī)練習(xí)題 ? 字符串距離（ TJU1086） ? 設(shè)有字符串 X，我們稱(chēng)在 X的頭尾及中間插入任意多個(gè)空格后構(gòu)成的新字符串為 X的擴(kuò)展串，如字符串 X為 “ abcbcd”，則字符串“ abcb□ cd”， “ □ a□ bcbcd□ ”和“ abcb□ cd□ ”都是 X的擴(kuò)展串，這里 “ □ ” 代表空格字符。 如果 A1是字符串 A的擴(kuò)展串， B1是字符串 B的擴(kuò)展串， A1與 B1具有相同的長(zhǎng)度，那么我們定義字符串 A1與 B1的距離為相應(yīng)位置上的字符的距離總和，而兩個(gè)非空格字符的距離定義為它們的 ASCII碼的差的絕對(duì)值，而空格字符與其它任意字符之間的距離為已知的定值 K，空格字符與空格字符的距離為 O。在字符串 A、 B的所有擴(kuò)展串中，必定存在兩個(gè)等長(zhǎng)的擴(kuò)展串 AB1，使得 A1與 B1之間的距離達(dá)到最小，我們將這一距離定義為字符串 A、 B的距離。 請(qǐng)你寫(xiě)一個(gè)程序，求出字符串 A、 B的距離。 動(dòng)規(guī)練習(xí)題 ? 二叉蘋(píng)果樹(shù)（ Ural1018） ? 有一棵蘋(píng)果樹(shù)，如果樹(shù)枝有分叉，一定是分 2叉（就是說(shuō)沒(méi)有只有 1個(gè)兒子的結(jié)點(diǎn)） 這棵樹(shù)共有 N個(gè)結(jié)點(diǎn)（葉子點(diǎn)或者樹(shù)枝分叉點(diǎn)），編號(hào)為 1N,樹(shù)根編號(hào)一定是 1。 我們用一根樹(shù)枝兩端連接的結(jié)點(diǎn)的編號(hào)來(lái)描述一根樹(shù)枝的位置。下面是一顆有 4個(gè)樹(shù)枝的樹(shù) 2 5 \ / 3 4 \ / 1 現(xiàn)在這顆樹(shù)枝條太多了，需要剪枝。但是一些樹(shù)枝上長(zhǎng)有蘋(píng)果。 給定需要保留的樹(shù)枝數(shù)量，求出最多能留住多少蘋(píng)果。 動(dòng)規(guī)練習(xí)題 ? 最長(zhǎng)前綴 IOI39。96amp。USACO ） ? 在生物學(xué)中，一些生物的結(jié)構(gòu)是用包含其要素的大寫(xiě)字母序列來(lái)表示的。生物學(xué)家對(duì)于把長(zhǎng)的序列分解成較短的（稱(chēng)之為元素的）序列很感興趣。如果一個(gè)集合 P 中的元素可以通過(guò)串聯(lián)組成一個(gè)序列 S ，那么我們認(rèn)為序列 S 可以分解為 P 中的元素。并不是所有的元素都必須出現(xiàn)。舉個(gè)例子，序列 ABABACABAAB 可以分解為下面集合中的元素： {A, AB, BA, CA, BBC} 序列 S 的前面 K 個(gè)字符稱(chēng)作 S 中長(zhǎng)度為 K 的前綴。設(shè)計(jì)一個(gè)程序，輸入一個(gè)元素集合以及一個(gè)大寫(xiě)字母序列，計(jì)算這個(gè)序列最長(zhǎng)的前綴的長(zhǎng)度。 動(dòng)規(guī)練習(xí)題 ? 祝福（ TJU1078） ? 得知 Atlantis即將沉沒(méi)的消息以后， King決定把他的人民送到安全的國(guó)外去。但是碼頭已經(jīng)廢棄很多很多年了。碼頭前有一個(gè)迷宮，國(guó)王的騎士只身闖入了這個(gè)迷宮 …… 騎士在迷宮的出口遇到了不明生物的襲擊！騎士因?yàn)槭菃为?dú)作戰(zhàn)，所以很快便招架不住了，他的大馬被打得奄奄一息（。）這個(gè)時(shí)候，迷宮中的兩座石像 (一個(gè)是貓老大，一個(gè)是天使。（?。。。?！ ))里放出了無(wú)數(shù)鋒利的刀片，把不明生物全部殺死，騎士當(dāng)場(chǎng)暈倒在地。等他醒來(lái)，發(fā)現(xiàn)馬已經(jīng)死了，手上多了一個(gè)戒指，上面寫(xiě)著： “ 這個(gè)戒指會(huì)幫助你逃脫。它賦予了神奇的力量。有了它，每次移動(dòng)如果是只要 |xx1|+|yy1|=P(P在輸入中給出 )，且 (x1, y1)不是障礙物，你就能實(shí)現(xiàn)(x, y) (x1, y1)的移動(dòng)！ ” (Angel暗自想：還有這么心黑的 …… )迷宮為 n*m的矩陣。騎士從 (n, m)到 (1, 1)。問(wèn)：在戒指的幫助下，騎士最少要多少步才能回到入口？在步數(shù)最少的前提下，總共有多少種辦法到達(dá)入口？注意，騎士不會(huì)傻到一直停留在原地不動(dòng)。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1