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