NOIP普及講座3-動態(tài)規(guī)劃1

從搜索到動態(tài)規(guī)劃點擊添加文本點擊添加文本點擊添加文本點擊添加文本引例（數塔問題）設有一個三角形的數塔，頂點為根結點，每個結點有一個整數值。從頂點出發(fā)，可以向左走或向右走，從根結點13出發(fā)向左、向右的路徑長度可以是： 13－11－7－14－7，其和為52 13－11－12－14－13，其和為63若要求從根結點開始， 請找出一條路徑，使 路徑之和最大,輸出路

徑的長度。1315141124131211876872612點擊添加文本點擊添加文本點擊添加文本點擊添加文本引例（數塔問題）【問題分析】 （1）貪心法點擊添加文本點擊添加文本點擊添加文本點擊添加文本引例（數塔問題）【問題分析】 （2）搜索：點擊添加文本點擊添加文本點擊添加文本點擊添加文本引例（數塔問題）【問題分析】

（3）動態(tài)規(guī)劃：

點擊添加文本點擊添加文本點擊添加文本點擊添加文本引例（數塔問題）

1315141124131211876872612點擊添加文本點擊添加文本點擊添加文本點擊添加文本動態(tài)規(guī)劃的基本概念（1）階段：把所給問題的過程，恰當地分為若干個相互聯系的階段，以便能按一定的次序去求解。（2）狀態(tài)：狀態(tài)表示每個階段開始所處的自然狀況和客觀條件，它描述了研究問題過程中的狀況。（3）決策：決策表示當過程處于某一階段的某個狀態(tài)時，可以作出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策。點擊添加文本點擊添加文本點擊添加文本點擊添加文本動態(tài)規(guī)劃的基本概念（4）策略和最優(yōu)策略：由所有階段的決策組成的決策序列稱為全過程策略，簡稱策略。在實際問題中，從決策允許集合中找出最優(yōu)效果的策略稱為最優(yōu)策略。（5）狀態(tài)轉移方程：狀態(tài)轉移方程是確定兩個相鄰階段狀態(tài)的演變過程。點擊添加文本點擊添加文本點擊添加文本點擊添加文本運用動態(tài)規(guī)劃的條件（1）最優(yōu)化

子問題的局部最優(yōu)將導致整個問題的全局最優(yōu)，即問題具有最優(yōu)子結構的性質。也就是說問題的一個最優(yōu)解中包含著子問題的一個最優(yōu)解。（2）無后效性

當前階段中的狀態(tài)只能由上一個階段中的狀態(tài)轉移方程得來，與其他階段的狀態(tài)沒有關系，特別是與未發(fā)生的階段狀態(tài)沒有關系，這就是無后效性。點擊添加文本點擊添加文本點擊添加文本點擊添加文本動態(tài)規(guī)劃算法的一般模式（1）劃分階段：按照問題的時間或空間特征，把問題分為若干個階段；（2）確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個階段時所處的各種情況用不同狀態(tài)表示出來；（3）確定決策并寫出狀態(tài)轉移方程：一般是根據相鄰兩個階段各狀態(tài)之間的關系來確定決策；（4）尋找邊界條件：給出的狀態(tài)轉移方程是一個遞推式，必須有一個遞推的邊界條件；（5）編寫程序。

點擊添加文本點擊添加文本點擊添加文本點擊添加文本經典例題講解【例題1】攔截導彈（noiopenjudge8780）問題描述：某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截系統(tǒng)。但是這種導彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導彈。輸入導彈依次飛來的高度（雷達給出的高度數據是不大于30000的正整數），計算這套系統(tǒng)最多能攔截多少導彈。點擊添加文本點擊添加文本點擊添加文本點擊添加文本經典例題講解輸入第一行是一個整數N（不超過15），表示導彈數。第二行包含N個整數，為導彈依次飛來的高度（雷達給出的高度數據是不大于30000的正整數）。輸出一個整數，表示最多能攔截的導彈數。樣例輸入838920715530029917015865樣例輸出6點擊添加文本點擊添加文本點擊添加文本點擊添加文本經典例題講解【問題分析】狀態(tài)：f[i]代表打下第i顆導彈最多能打多少顆導彈方程：f[i]=max(f[j])+1(1<=j<i)且第i顆導彈的高度要高于第j顆導彈的高度

點擊添加文本點擊添加文本點擊添加文本點擊添加文本【程序實現】

點擊添加文本點擊添加文本點擊添加文本點擊添加文本經典例題講解【例題2】饑餓的牛問題描述：牛在飼料槽前排好了隊。飼料槽依次用1到N(1<=N<=2000)編號。每天晚上，一頭幸運的牛根據約翰的規(guī)則，吃其中一些槽里的飼料。約翰提供B個區(qū)間的清單。一個區(qū)間是一對整數start-end,1<=start<=end<=N，表示一些連續(xù)的飼料槽，比如1-3,7-8,3-4等等。牛可以任意選擇區(qū)間，但是牛選擇的區(qū)間不能有重疊。當然，牛希望自己能夠吃得越多越好。給出一些區(qū)間，幫助這只牛找一些區(qū)間，使它能吃到最多的東西。在上面的例子中，1-3和3-4是重疊的；聰明的牛選擇{1-3，7-8}，這樣可以吃到5個槽里的東西。點擊添加文本點擊添加文本點擊添加文本點擊添加文本經典例題講解【輸入格式】第一行，整數B(1<=B<=1000)第2到B+1行，每行兩個整數，表示一個區(qū)間，較小的端點在前面【輸出格式】僅一個整數，表示最多能吃到多少個槽里的食物?！緲永斎搿?137834【樣例輸出】5

點擊添加文本點擊添加文本點擊添加文本點擊添加文本經典例題講解【問題分析】狀態(tài)：f[i]代表吃了第i個區(qū)間最多能多少食物方程：f[i]=max(f[j])+i個區(qū)間的長度(1<=j<i)且第i顆區(qū)間的開始時間要大于j的區(qū)間的結束時間

點擊添加文本點擊添加文本點擊添加文本點擊添加文本經典例題講解【例題3】最長公共子序列（codevs1408）問題描述：熊大媽的奶牛在小沐沐的熏陶下開始研究信息題目。小沐沐先讓奶牛研究了最長上升子序列，再讓他們研究了最長公共子序列，現在又讓他們要研究最長公共上升子序列了。小沐沐說，對于兩個串A，B，如果它們都包含一段位置不一定連續(xù)的數字，且數字是嚴格遞增的，那么稱這一段數字是兩個串的公共上升子串，而所有的公共上升子串中最長的就是最長公共上升子串了。奶牛半懂不懂，小沐沐要你來告訴奶牛什么是最長公共上升子串。不過，只要告訴奶牛它的長度就可以了。點擊添加文本點擊添加文本點擊添加文本點擊添加文本經典例題講解【輸入格式】第一行N，表示A，B的長度。第二行，串A。第三行，串B。【輸出格式】輸出長度【樣例輸入】422132123【樣例輸出】2【數據范圍及提示】1<=N<=3000，A，B中的數字不超過maxlongint點擊添加文本點擊添加文本點擊添加文本點擊添加文本經典例題講解【問題分析】

狀態(tài)

f[i,j]代表a字符串到i,b字符串到j的最長公共字串方程：

a[i]=a[j]則f[i,j]=f[i-1,j-1]+1;a[i]不等于a[j]則f[i,j]=max(f[i-1,j],f[i,j-1])點擊添加文本點擊添加文本點擊添加文本點擊添加文本【程序實現】

點擊添加文本點擊添加文本點擊添加文本點擊添加文本【程序實現】

點擊添加文本點擊添加文本點擊添加文本點擊添加文本經典例題講解【例題4】最低通行費用（noiopenjudge7614）問題描述：一個商人穿過一個N*N的正方形的網格，去參加一個非常重要的商務活動。他要從網格的左上角進，右下角出。每穿越中間1個小方格，都要花費1個單位時間。商人必須在(2N-1)個單位時間穿越出去。而在經過中間的每個小方格時，都需要繳納一定的費用。這個商人期望在規(guī)定時間內用最少費用穿越出去。請問至少需要多少費用？注意：不能對角穿越各個小方格（即，只能向上下左右四個方向移動且不能離開網格）。輸入第一行是一個整數，表示正方形的寬度N(1<=N<100)；后面N行，每行N個不大于100的整數，為網格上每個小方格的費用。輸出至少需要的費用.點擊添加文本點擊添加文本點擊添加文本點擊添加文本經典例題講解樣例輸入51468102571517689182010111219212023252933樣例輸出109提示樣例中，最小值為109=1+2+5+7+9+12+19+21+33。點擊添加文本點擊添加文本點擊添加文本點擊添加文本經典例題講解【問題分析】狀態(tài)：f[i,j]代表到達i,j位置的最低費用方程：f[i,j]=max(f[i-1,j],f[i,j-1])+a[i,j];

點擊添加文本點擊添加文本點擊添加文本點擊添加文本【程序實現】

點擊添加文本點擊添加文本點擊添加文本點擊添加文本經典例題講解【例題5】機器分配問題描述：某總公司擁有高效生產設備M臺，準備分給下屬的N個分公司。各分公司若獲得這些設備，可以為總公司提供一定的盈利。問：如何分配這M臺設備才能使國家得到的盈利最大？求出最大盈利值。分配原則：每個公司有權獲得任意數目的設備，但總臺數不得超過總設備數M。其中M<=100，N<=100。點擊添加文本點擊添加文本點擊添加文本點擊添加文本經典例題講解【輸入格式】第一行為兩個整數M，N。接下來是一個N×M的矩陣，其中矩陣的第i行的第j列的數Aij表明第i個公司分配j臺機器的盈利。所有數據之間用一個空格分隔?！据敵龈袷健恐挥幸粋€數據，為總公司分配這M臺設備所獲得的最大盈利?！緲永斎搿?2123234【樣例輸出】4點擊添加文本點擊添加文本點擊添加文本點擊添加文本經典例題講解【問題分析】狀態(tài)：f[i,j]代表前i個公司分配到j臺設備所能獲得的最大盈利方程f[i,j]=max(f[i-1,j-k]+a[i,k])0<=k<=j

點擊添加文本點擊添加文本點擊添加文本點擊添加文本【程序實現】

點擊添加文本點擊添加文本點擊添加文本點擊添加文本經典例題講解【例題6】復制書稿問題描述：有M本書（編號為1，2，…，M），每本書都有一個頁數（分別是P1，P2，…，PM）。想將每本都復制一份。將這M本書分給K個抄寫員（1<=K<=M<=500)，每本書只能分配給一個抄寫員進行復制。每個抄寫員至少被分配到一本書，而且被分配到的書必須是連續(xù)順序的。復制工作是同時開始進行的，并且每個抄寫員復制一頁書的速度都是一樣的。所以，復制完所有書稿所需時間取決于分配得到最多工作的那個抄寫員的復制時間。試找一個最優(yōu)分配方案，使分配給每一個抄寫員的頁數的最大值盡可能小。（假設復制一頁需要1分鐘）點擊添加文本點擊添加文本點擊添加文本點擊添加文本經典例題講解【輸入格式】第一行兩個整數M、K；（K<=M<=100）第二行M個整數，第i個整數表示第i本書的頁數?！据敵龈袷健抗?行，復制完所有書最少用的時間（分鐘）【輸入樣例】93123456789【輸出樣例】17點擊添加文本點擊添加文本點擊添加文本點擊添加文本經典例題講解【問題分析】狀態(tài)f[i,j]代筆前i個人寫j本書所需要的最少時間。方程：f[i,j]=min(max(f[i-1,k],s[j]-s[k]))i-1<=k<=j-1

點擊添加文本點擊添加文本點擊添加文本點擊添加文本【程序實現】

點擊添加文本點擊添加文本點擊添加文本點擊添加文本動態(tài)規(guī)劃小結

求得的一個最優(yōu)解當前階段的決策僅受前一階段決策的影響，并決定下一個階段的決策當前階段i多個規(guī)劃(決策)當前最優(yōu)決策當前非最優(yōu)決策i向著目標階段不斷改變(動態(tài))規(guī)劃方向目標階段初始階段動態(tài)規(guī)劃點擊添加文本點擊添加文本點擊添加文本點擊添加文本動態(tài)規(guī)劃小結

動態(tài)規(guī)劃和一般遞推的