動(dòng)態(tài)規(guī)劃專題講義(編輯修改稿)
2024-08-14 12:39 本頁面
【文章內(nèi)容簡(jiǎn)介】 ,最后的答案也就是 F[length(s),m]. ?于是就有一個(gè)動(dòng)規(guī)的方程 : F[i,j]:=min(f[i,j],f[k,j1]+num[k+1,i]) num[k+1,i]表示 k+1位到 i位所形成的數(shù)字 .這里顯然是把加號(hào)插入了第 k+1個(gè)位置上 . ?知道了這一題怎么做以后 ,乘積最大的一題也是完全一樣的形式 ,誰還會(huì)去用搜索 ? 定量 ?現(xiàn)在大概大家已經(jīng)了解了定量是什么 ,那么我們下面通過幾道題目來了解一下定量的威力 . 游戲 ?游戲 (Noip2022普及組 ) ?這一題的描述簡(jiǎn)單說一下 :在一個(gè)圈的周圍有 n個(gè)石子 ,將他們劃分成 m堆 (每堆中的石子必須連續(xù)相鄰 ),每一堆石子計(jì)算出他們的總重量 mod10的值 ,然后將這些值相乘 ,求得到的結(jié)果最大最小值是多少 . 游戲 ?這一題作者其實(shí)是根據(jù)最佳加法表達(dá)式改編的 .但是他加了一個(gè)在圈上的條件 ,怎么辦呢 ? 尋找定量 ! 游戲 ? 可想而知 ,因?yàn)橹辽僖殖?1堆 ,那么至少有兩個(gè)石子之間是會(huì)被分隔開的 .這就是定量 !當(dāng)劃分?jǐn)?shù) 1時(shí) ,一定有兩個(gè)相鄰石子被劃分到不同的堆里去 ! ? 于是這個(gè)圈被這樣的理解斷成了一條線 ,解法就和最佳加法表達(dá)式一樣了 . ? 當(dāng)然這個(gè)斷開的位置是需要枚舉的 ,然后保留下一個(gè)最優(yōu)值 .顯然這個(gè)斷開的操作對(duì)整個(gè)過程沒有影響 ,因?yàn)檫@是必然的情況 ,這是定量 ! 最優(yōu)三角形劃分 ?問題描述 ?給定一具有 N（ N50）個(gè)頂點(diǎn) (從1到 N編號(hào)）的凸多邊形，每個(gè)頂點(diǎn)的權(quán)均已知。問如何把這個(gè)凸多邊形劃分成 N2個(gè)互不相交的三角形，使得這些三角形頂點(diǎn)的權(quán)的乘積之和最小？ 最優(yōu)三角形劃分 ? 這一題大概搜都是十分麻煩的 ,可是這一題 Dp的話 ,比搜索要容易實(shí)現(xiàn)和容易理解得多 . ? 先得表示一下狀態(tài) ,我們用 f[i,j]表示以第 i個(gè)點(diǎn)開頭 ,順時(shí)針長(zhǎng)度為 j的一塊子多邊形 .如上圖中 f[1,5]表示的子多邊形 (黑色虛線劃開 ) 最優(yōu)三角形劃分 ? 如果沒有紅色虛線的部分 ,或許你會(huì)認(rèn)為決策應(yīng)該是枚舉子多邊形內(nèi)的兩點(diǎn)連線 ,然后分成兩個(gè)子多邊形 .這顯然是不行的 ,因?yàn)橛?jì)算機(jī)已經(jīng)無法再表示分割出來的子多邊形了 (不能用 f[i,j]來表示了 ). 最優(yōu)三角形劃分 ? 那么我們?cè)撊绾螞Q策呢 ?尋找定量 ! ? 顯然可以發(fā)現(xiàn) ,f[i,j]表示的子多邊形有一條邊是在內(nèi)部的 (黑色虛線 ),而這一條邊在該子多邊形內(nèi)必定屬于某個(gè)三角形 ,因?yàn)槲覀冞x擇了該子多邊形作為一種狀態(tài) ,那么就一定存在那條虛線黑邊 ,所以一定存在所說的三角形 .于是我們枚舉這個(gè)三角形的另外一個(gè)點(diǎn)在子多邊形的位置 ,則可以把子問題還原到原問題 (因?yàn)樵撊切伟讯噙呅蝿澇闪藘蓚€(gè)可以用表示的多邊形和一個(gè)三角形 ).這些再次分割出的子多邊形就是以前狀態(tài) ,而剛才的多邊形則是當(dāng)前狀態(tài) . 定量 ?其實(shí)定量的作用就是為了寫出狀態(tài)轉(zhuǎn)移方程 ,即讓人能迅速找出狀態(tài)之間的關(guān)系 (決策 ).通過定量的處理 ,當(dāng)前狀態(tài)又回到了以前狀態(tài) ,選手就可以知道 ,這一題就是要用動(dòng)態(tài)規(guī)劃來求解了 . 定量 ? 我們來看看剛才的一些題目的定量 . ? 交錯(cuò)匹配 :一定存在最后一組交錯(cuò)(這好像是廢話 ),所以枚舉這個(gè)最后的交錯(cuò)的位置作為狀態(tài) ,這樣就回到以前狀態(tài) . ? 買車票 :定量 1:一定有最后一個(gè)車站(這個(gè)作為狀態(tài) )。定量 2:某個(gè)車站一定是由某個(gè)前面的車站到達(dá)的 .(導(dǎo)彈攔截也是這樣 ) ? 數(shù)字三角形 :某個(gè)點(diǎn)一定是由他上面的相鄰兩點(diǎn)到達(dá)的 .(過河卒也是這樣 ) 定量很不錯(cuò)啊 ! 動(dòng)態(tài)規(guī)劃的武器 ?在動(dòng)規(guī)的操作過程中 ,或者是操作過程前 ,有一些很常用的武器 ,這里簡(jiǎn)要介紹兩種 : 排序 ?武器一 :排序 ?遇到過很多需要排序的動(dòng)態(tài)規(guī)劃題目 ,如果不排序 ,動(dòng)規(guī)的思想很難體現(xiàn) . Tom的煩惱 ? Tom的煩惱 這是大家熟知的一題 ,如果不排序的話 ,復(fù)雜度便是 N^2,按起始時(shí)間排序復(fù)雜度也是 N^2,二按結(jié)束時(shí)間排序之后復(fù)雜度降為了 NlogN. 巴比倫塔 ?巴比倫塔 ?問題描述 : 有很多的不同種類的立方體 (長(zhǎng)寬高不同 ),每一類有無限多個(gè) .將他們一層層的疊加起來 ,要求上面的一塊立方體的下底面一定要比下面的一塊立方體的上底面要小 ,就是長(zhǎng)和寬都要小于 .問最多能建成多高的塔 . 巴比倫塔 ? 經(jīng)過研究可以發(fā)現(xiàn) ,每一種類的立方體有 3種不同的擺放方式 ,而每種擺放方式最多用 1次 ,所以可以分離出3*N塊“不同”的立方體 ,接下來 ,或許你仍然不知道如何動(dòng)規(guī) ,那么就試試排序 .列出所有的石塊的所有擺放方式 xi,yi, xiyi或者 xi xi,yi,zi的大小順序排序 .這樣就可以進(jìn)行十分簡(jiǎn)單的類似與導(dǎo)彈攔截的一個(gè)動(dòng)態(tài)規(guī)劃的處理了 .限制條件是 xi和 yi,代價(jià)值是 zi(高度 ). 滑雪 ?滑雪 (上海 2022) ?題目的大意是給出一個(gè)矩陣 ,如 : 對(duì)于所給出的矩陣找出一條最長(zhǎng)的遞減鏈 ,滿足鏈中相鄰的兩個(gè)元素間都是在矩陣中相鄰的 . 上圖中所給出的矩陣中的最長(zhǎng)鏈 是 1 2 3 4……25. 滑雪 ?對(duì)于有給出的數(shù)字進(jìn)行遞減排序 ,然后兩重循環(huán)就搞定問題 .動(dòng)態(tài)轉(zhuǎn)移方程是 : F[i]:=max(F[i],F[j]+1)。 滿足條件是 i與 j在原矩陣中相鄰 . ?試想 ,如果你不知道要排序 ,你能想到這題是用動(dòng)態(tài)規(guī)劃嗎 ? 填鴨 ?武器二 :填鴨 ?這個(gè)思想帶有枚舉
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1