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