動態(tài)規(guī)劃專題講義(文件)
【正文】 是為了寫出狀態(tài)轉移方程 ,即讓人能迅速找出狀態(tài)之間的關系 (決策 ).通過定量的處理 ,當前狀態(tài)又回到了以前狀態(tài) ,選手就可以知道 ,這一題就是要用動態(tài)規(guī)劃來求解了 . 定量 ? 我們來看看剛才的一些題目的定量 . ? 交錯匹配 :一定存在最后一組交錯(這好像是廢話 ),所以枚舉這個最后的交錯的位置作為狀態(tài) ,這樣就回到以前狀態(tài) . ? 買車票 :定量 1:一定有最后一個車站(這個作為狀態(tài) )。動規(guī)過程如下： f[0]:=true。 商店購物 ?商店購物 (IOI) 這一題更是需要開一個五維bool型數(shù)組 .還需要通過遞歸求出組合形式 .動規(guī)的方程我就不寫了 . 動態(tài)規(guī)劃的武器 ?講完了比較實用的兩種種動規(guī)的武器之后 ,我們來看看一些大家可能不太會做的動規(guī)類型 特殊的動規(guī) ?這里我講講三種特殊的動態(tài)規(guī)劃 :圖狀動規(guī) ,樹狀動規(guī) ,二次動規(guī) . 圖狀動規(guī) ? 城堡 ? 某國聰明美麗的公主要找一位如意郎君，她希望未來的夫君是一個聰明善良，節(jié)儉但又不吝嗇的人?，F(xiàn)在已知每個人的活躍指數(shù)和上司關系（當然不可能存在環(huán)），求邀請哪些人來能使得晚會的總活躍指數(shù)最大。分別可以用 f[i,1]和f[i,0]表示。 ?這就是樹狀動規(guī)的基本形態(tài)。而如果要到第 i層的第 j個房間買票，那么必須先在第 i1層的第 j個房間買票或者在第 i層的與這個房間相鄰的房間買過票才行 .而每個房間所要收取的票費是不同的 ,給定每個房間內(nèi)買票需要的費用 ,問要在第 n層的任意一間房間內(nèi)買到票的最小消費是多少 . 買票 ? 顯然不能寫這樣的狀態(tài)轉移方程 :f[i,j]:=min(f[i1,j],f[i,j1],f[i,j+1])+w[j].因為無法有一種處理順序使得在 f[i,j]之前同時求得 f[i,j1]和 f[i,j+1]的最優(yōu)值 . ? 所以動規(guī)分兩次進行 .第一次用狀態(tài)轉移方程 f[i,j]:=min(f[i,j1],f[i1,j])+w[i]求出一個不一定是最優(yōu)的解 .再用f[i,j]:=min(f[i,j],f[i,j+1],j from m1 downto 1)+w[i]求出最終的最優(yōu)解 ,可以證明這樣的能夠求出真正的最優(yōu)解 . ? 要注意的是這兩次動規(guī)不能分開做 ,而要在處理每一層的時候都要做 ,要不然顯然無法求得最優(yōu)值。這里 N=10000 網(wǎng)絡 ? 枚舉每個點，然后 DFS復雜度 O(N2)，超時是顯然的事情。 網(wǎng)絡 ? 第一次動規(guī)做 f[i]:=max(f[son])+1，第二次動規(guī)做 f[i]:=max(f[i],f[father] + 1) 。問題就解決了。 “ 垃圾井 ” 是農(nóng)夫們?nèi)永牡胤?，它的深度?D (2 = D = 100)英尺。假設卡門預先知道了每個垃圾扔下的時間 t(0 t = 1000)，以及每個垃圾堆放的高度 h(1 = h = 25)和吃進該垃圾能維持生命的時間 f(1 = f = 30)，要求出卡門最早能逃出井外的時間，假設卡門當前體內(nèi)有足夠持續(xù)10小時的能量，如果卡門 10小時內(nèi)沒有進食，卡門就將餓死。 請你寫一個程序，求出字符串 A、 B的距離。但是一些樹枝上長有蘋果。USACO ） ? 在生物學中，一些生物的結構是用包含其要素的大寫字母序列來表示的。舉個例子，序列 ABABACABAAB 可以分解為下面集合中的元素： {A, AB, BA, CA, BBC} 序列 S 的前面 K 個字符稱作 S 中長度為 K 的前綴。碼頭前有一個迷宮，國王的騎士只身闖入了這個迷宮 …… 騎士在迷宮的出口遇到了不明生物的襲擊！騎士因為是單獨作戰(zhàn)，所以很快便招架不住了，他的大馬被打得奄奄一息（。它賦予了神奇的力量。 。騎士從 (n, m)到 (1, 1)。（?。。。。?))里放出了無數(shù)鋒利的刀片，把不明生物全部殺死，騎士當場暈倒在地。 動規(guī)練習題 ? 祝福（ TJU1078） ? 得知 Atlantis即將沉沒的消息以后， King決定把他的人民送到安全的國外去。如果一個集合 P 中的元素可以通過串聯(lián)組成一個序列 S ，那么我們認為序列 S 可以分解為 P 中的元素。 動規(guī)練習題 ? 最長前綴 IOI39。 我們用一根樹枝兩端連接的結點的編號來描述一根樹枝的位置。 如果 A1是字符串 A的擴展串， B1是字符串 B的擴展串， A1與 B1具有相同的長度，那么我們定義字符串 A1與 B1的距離為相應位置上的字符的距離總和，而兩個非空格字符的距離定義為它們的 ASCII碼的差的絕對值，而空格字符與其它任意字符之間的距離為已知的定值 K，空格字符與空格字符的距離為 O。另外，卡門可以通過吃一些垃圾來維持自己的生命。 總結 ?動態(tài)規(guī)劃有很多東西還需要我們更加努力地去探索和學習 .總體上說來 ,動態(tài)規(guī)劃是個既簡單又不簡單的算法 ,熟練地掌握了動態(tài)規(guī)劃 ,也就熟練地控制了比賽 . That’s all! Thank you for listening. 動規(guī)練習題 ? 垃圾陷阱（ USACOamp。 ? 不要放棄，在實際操作過程中， f需要記下兩個值，一個是最優(yōu)值，一個是次優(yōu)值，這兩個值必須由不用的子結點得到。 ? 樹上的動規(guī)，是否直接可以寫出下面的狀態(tài)轉移方城呢？ ? f[i]:=max(f[son],f[father])+1 ? 廢話，顯然是不行的， son和 father的值不可能同時得到。每個結點延樹的邊可以走到樹的任意一個結點，令 Ai為第 i個結點最遠能走的距離，求出 Ai最小的結點有哪些。 ? 買票 ? 有一座 n層的樓房，某個人要到第 n層的任何一個房間買票
環(huán)評公示相關推薦
鄂ICP備17016276號-1