[計算機(jī)]DP-坐標(biāo)規(guī)則型動態(tài)規(guī)劃ppt課件

1、坐標(biāo)規(guī)那么型動態(tài)規(guī)坐標(biāo)規(guī)那么型動態(tài)規(guī)劃劃Robots 在一個在一個n*m的棋盤內(nèi)，一些格子里有垃圾要的棋盤內(nèi)，一些格子里有垃圾要拾撿。如今有一個能撿垃圾的機(jī)器人從左拾撿。如今有一個能撿垃圾的機(jī)器人從左上格子里出發(fā)，每次只能向右或者向下走。上格子里出發(fā)，每次只能向右或者向下走。每次他到達(dá)一個點(diǎn)，就會自動把這個點(diǎn)內(nèi)每次他到達(dá)一個點(diǎn)，就會自動把這個點(diǎn)內(nèi)的垃圾拾掉。的垃圾拾掉。 問：最多能拾多少垃圾。在最多的情況下，問：最多能拾多少垃圾。在最多的情況下，有多少種拾垃圾方案？有多少種拾垃圾方案？ 數(shù)據(jù)范圍數(shù)據(jù)范圍:n=100,m=100樣例分析 最多能拾最多能拾5塊。有塊。有4種方法。種方法。分析1 因

2、為機(jī)器人只能向右或者向下走。符合無因?yàn)闄C(jī)器人只能向右或者向下走。符合無后效性原那么。于是考慮動態(tài)規(guī)劃。后效性原那么。于是考慮動態(tài)規(guī)劃。 設(shè)設(shè)Fi,j表示從表示從1,1點(diǎn)開場走到點(diǎn)開場走到i,j的時候，最多撿了多少垃圾。的時候，最多撿了多少垃圾。 Fi,j=Maxfi-1,j,fi,j-1+ci,j 其中其中Ci,j=1表示表示i,j點(diǎn)有垃圾。點(diǎn)有垃圾。Ci,j=0表示沒有表示沒有 1=i=n,1=j=m，決策，決策2種種 時間復(fù)雜度為時間復(fù)雜度為On*m分析2 設(shè)設(shè)Gi,j表示在表示在fi,j最大的時候，有多少種方最大的時候，有多少種方案。案。 撿到撿到fi,j的垃圾只能從兩個方向來走，的垃圾

3、只能從兩個方向來走，方案數(shù)累加即可。因此，方案數(shù)累加即可。因此，gi,j=gi-1,j*k+gi,j-1*L假如假如fi-1,j+ci,j=fi,j，那么，那么K=1否那么否那么K=0。假如假如fi,j-1+ci,j=fi,j，那么，那么L=1否那么否那么L=0 時間復(fù)雜度時間復(fù)雜度On*m 矩陣取數(shù)游戲矩陣取數(shù)游戲 NOIP2007 對于一個給定的對于一個給定的n*m的矩陣，矩陣中的每個元素的矩陣，矩陣中的每個元素aij為非負(fù)整數(shù)。游戲規(guī)那么如下：為非負(fù)整數(shù)。游戲規(guī)那么如下：1. 每次取數(shù)時須從每行各取走一個元素，共每次取數(shù)時須從每行各取走一個元素，共n個。個。 m次次后取完矩陣所有的元素；

4、后取完矩陣所有的元素；2. 每次取走的各個元素只能是該元素所在行的行首或行每次取走的各個元素只能是該元素所在行的行首或行尾；尾；3. 每次取數(shù)都有一個得分值，為每行取數(shù)的得分之和；每次取數(shù)都有一個得分值，為每行取數(shù)的得分之和；每行取數(shù)的得分每行取數(shù)的得分 = 被取走的元素值被取走的元素值* *2i，其中，其中i表示第表示第i次取數(shù)從次取數(shù)從1開場編號；開場編號；4. 游戲完畢總得分為游戲完畢總得分為m次取數(shù)得分之和。次取數(shù)得分之和。 求出取數(shù)后的最大得分。求出取數(shù)后的最大得分。樣例 輸入輸入 2 31 2 33 4 2 輸出輸出82 第第1次：第一行取行首元素，第二行取行尾元素，次：第一行取行

5、首元素，第二行取行尾元素，本次的氣氛本次的氣氛1*21+2*21=6 第第2次：兩行均取行首元素，本次得分為次：兩行均取行首元素，本次得分為2*22+3*22=20 第第3次：得分為次：得分為3*23+4*23=56。總得分為?？偟梅譃?+20+56=82數(shù)據(jù)范圍 60%的數(shù)據(jù)滿足：1=n, m=30，答案不超過1016 100%的數(shù)據(jù)滿足：1=n, m=80，0=aij=1000 1*21+2*21=6 2*22+3*22=20 3*23+4*23=561*21+2*22+3*23= 2*21+3*22+4*23分析分析 首先，首先，n行求值可以獨(dú)立考慮！行求值可以獨(dú)立考慮！ 設(shè)設(shè)fi,j表

6、示區(qū)間表示區(qū)間i-j的最優(yōu)值的最優(yōu)值 fi,j=maxfi+1,j+w*ai , fi,j-1+w*aj 其中其中w=w+w,即即w*2 需要做假設(shè)干次高精度加法和乘法。需要做假設(shè)干次高精度加法和乘法。 直到求出，直到求出，maxfi,i+w*ai，i=1.m為止。為止。傳紙條傳紙條NOIP2020 小淵坐在矩陣的左上角，坐標(biāo)小淵坐在矩陣的左上角，坐標(biāo)1,1，小軒坐在矩陣的，小軒坐在矩陣的右下角，坐標(biāo)右下角，坐標(biāo)m,n。從小淵傳到小軒的紙條只可以向。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。向左傳遞

7、。 班里每個同學(xué)都可以幫他們傳遞，但只會幫他們一次。班里每個同學(xué)都可以幫他們傳遞，但只會幫他們一次。 每個同學(xué)愿意幫助的好感度有高有低，可以用一個每個同學(xué)愿意幫助的好感度有高有低，可以用一個0-100的自然數(shù)來表示，數(shù)越大表示越好心。的自然數(shù)來表示，數(shù)越大表示越好心。 小淵和小軒希望盡可能找好心程度高的同學(xué)來幫助傳紙條小淵和小軒希望盡可能找好心程度高的同學(xué)來幫助傳紙條，即找到來回兩條傳遞途徑，使得這兩條途徑上同學(xué)的好，即找到來回兩條傳遞途徑，使得這兩條途徑上同學(xué)的好心程度只和最大。如今，請你幫助小淵和小軒找到這樣的心程度只和最大。如今，請你幫助小淵和小軒找到這樣的兩條途徑。兩條途徑。 1=m,

8、n=50貪心 很容易想到一個算法：很容易想到一個算法： 求出求出1個紙條從個紙條從1，1到到M,N的道路最大值的道路最大值. 刪除途徑上的點(diǎn)值刪除途徑上的點(diǎn)值 再求出再求出1個紙條從個紙條從M,N 到到1，1的道路最大值的道路最大值. 統(tǒng)計兩次和統(tǒng)計兩次和 上述算法很容易找出反例，如以下圖。上述算法很容易找出反例，如以下圖。 第第1次找最優(yōu)值傳遞后，導(dǎo)致第次找最優(yōu)值傳遞后，導(dǎo)致第2次無法傳遞。次無法傳遞。分析 貪心算法錯誤，因此我們需要同時考慮兩個紙條的傳遞。貪心算法錯誤，因此我們需要同時考慮兩個紙條的傳遞。 由于由于小淵小淵和小軒的途徑可逆，因此，盡管出發(fā)點(diǎn)不同，但和小軒的途徑可逆，因此，盡

9、管出發(fā)點(diǎn)不同，但都可以看成同時從都可以看成同時從1,1出發(fā)到達(dá)出發(fā)到達(dá)M,N點(diǎn)。點(diǎn)。 設(shè)設(shè)fi1,j1,i2,j2表示紙條表示紙條1到達(dá)到達(dá)i1,j1位置，紙條位置，紙條2到達(dá)到達(dá)i2,j2位置的最優(yōu)值。那么有，位置的最優(yōu)值。那么有， 其中其中 i1,j1 i2,j2 1=i1, i2=M, 1=j1 , j2=N 時間復(fù)雜度時間復(fù)雜度ON2M2,) 1, 1,() 1, 1(), 1, 1,(), 1, 1(max),(221122112211221122112211jiCjiCjijifjijifjijifjijifjijif分析2 另一種思路：每個紙條都需要走另一種思路：每個紙條都需要走

10、M+N步才能到達(dá)目的。步才能到達(dá)目的。 因此，設(shè)因此，設(shè)Fk,i1,i2表示兩個紙條都走了表示兩個紙條都走了K步，第步，第1個紙條個紙條橫坐標(biāo)為橫坐標(biāo)為i1,第第2個紙條橫坐標(biāo)為個紙條橫坐標(biāo)為i2的最優(yōu)值。的最優(yōu)值。 那么兩個紙條的縱坐標(biāo)分別為那么兩個紙條的縱坐標(biāo)分別為j1=K-i1, j2=K-i2 ,狀態(tài)轉(zhuǎn)移方狀態(tài)轉(zhuǎn)移方程如下：程如下： 其中其中 i1i2 1=i1, i2=M,1=k=N+M 時間復(fù)雜度時間復(fù)雜度ON+M*M2,) 1, 1, 1() 1, 1(), 1, 1(), 1(max),(22112121212121ikiCikiCiikfiikfiikfiikfiikf免費(fèi)餡

11、餅免費(fèi)餡餅 SERKOISERKOI最新推出了一種叫做最新推出了一種叫做“免費(fèi)餡餅免費(fèi)餡餅的游戲。的游戲。 游戲在一個舞臺上進(jìn)展。舞臺的寬度為游戲在一個舞臺上進(jìn)展。舞臺的寬度為W W格，天幕的高度格，天幕的高度為為H H格，游戲者占一格。開場時，游戲者站在舞臺的正中格，游戲者占一格。開場時，游戲者站在舞臺的正中央，手里拿著一個托盤。央，手里拿著一個托盤。 游戲開場后，從舞臺天幕頂端的格子中不斷出現(xiàn)餡餅并游戲開場后，從舞臺天幕頂端的格子中不斷出現(xiàn)餡餅并垂直下落。游戲者左右挪動去接餡餅。游戲者每秒可以垂直下落。游戲者左右挪動去接餡餅。游戲者每秒可以向左或右挪動一格或兩格，也可以站在愿地不動。向左或

12、右挪動一格或兩格，也可以站在愿地不動。 餡餅有很多種，游戲者事先根據(jù)自己的口味，對各種餡餡餅有很多種，游戲者事先根據(jù)自己的口味，對各種餡餅依次打了分。同時在餅依次打了分。同時在8-3088-308電腦的遙控下，各種餡餅下電腦的遙控下，各種餡餅下落的速度也是不一樣的，下落速度以格落的速度也是不一樣的，下落速度以格/ /秒為單位。當(dāng)餡秒為單位。當(dāng)餡餅在某一秒末恰好到達(dá)游戲者所在的格子中，游戲者就餅在某一秒末恰好到達(dá)游戲者所在的格子中，游戲者就搜集到了這塊餡餅。搜集到了這塊餡餅。 寫一個程序，幫助我們的游戲者搜集餡餅，使得搜集的寫一個程序，幫助我們的游戲者搜集餡餅，使得搜集的餡餅的分?jǐn)?shù)之和最大。餡餅

13、的分?jǐn)?shù)之和最大。 輸入數(shù)據(jù)：輸入數(shù)據(jù)：第一行第一行:寬度寬度W199奇數(shù)和高度奇數(shù)和高度H1 100整數(shù)整數(shù)接下來給出了一塊餡餅信息。由接下來給出了一塊餡餅信息。由4個正整數(shù)組成，分別表個正整數(shù)組成，分別表示了餡餅的示了餡餅的初始下落時刻、程度位置、下落速度、分值。初始下落時刻、程度位置、下落速度、分值。游戲開場時刻為游戲開場時刻為0。從。從1開場自左向右依次對程度方向的每開場自左向右依次對程度方向的每格編號。格編號。 輸出數(shù)據(jù)：輸出數(shù)據(jù)：搜集到的餡餅最大分?jǐn)?shù)之和。搜集到的餡餅最大分?jǐn)?shù)之和。 由上圖可知，盡管下落了由上圖可知，盡管下落了4個餡餅，但只能接到個餡餅，但只能接到3個個： 第第1時刻

14、可以接到分值為時刻可以接到分值為5的餡餅的餡餅 第第2時刻可以接到分值為時刻可以接到分值為3的餡餅的餡餅 第第3時刻可以接到分值為時刻可以接到分值為4的餡餅的餡餅 因此餡餅的總分值為因此餡餅的總分值為5+3+4=12分析 由于餡餅下落的時間和速度都不同，人只能向左右挪動，由于餡餅下落的時間和速度都不同，人只能向左右挪動，餡餅只能向下挪動。人和餡餅都同時挪動，考慮起來比較餡餅只能向下挪動。人和餡餅都同時挪動，考慮起來比較復(fù)雜，因此我們需要轉(zhuǎn)變思路：復(fù)雜，因此我們需要轉(zhuǎn)變思路：算出每個時刻落到最底算出每個時刻落到最底層的每個格子有多少分層的每個格子有多少分值的餡餅。值的餡餅。假如將餡餅當(dāng)成參照物，

15、假如將餡餅當(dāng)成參照物，那么餡餅向下落，可以那么餡餅向下落，可以看成餡餅不動，人往上看成餡餅不動，人往上走去摘取餡餅，這樣人走去摘取餡餅，這樣人每每1時刻都可以走到上時刻都可以走到上一行的一行的5個格子，如右個格子，如右圖：圖：動態(tài)規(guī)劃動態(tài)規(guī)劃 計算出每個格子每個時刻可能到達(dá)的餡餅分值，填入計算出每個格子每個時刻可能到達(dá)的餡餅分值，填入W*H的天幕表。的天幕表。 其中其中Ci,j表示天幕的第表示天幕的第i行第行第j列的餡餅分值，即第列的餡餅分值，即第i時時刻，餡餅落到最底行的餡餅分值?？?，餡餅落到最底行的餡餅分值。 設(shè)設(shè)Fi,j表示人走到第表示人走到第i行行j列所獲得的餡餅最大分值列所獲得的餡餅

16、最大分值和，那么有，和，那么有， 0=i=T,1=j=W,決策數(shù)為決策數(shù)為5個個 時間復(fù)雜度為時間復(fù)雜度為O5WT,)2, 1() 1, 1(), 1() 1, 1()2, 1(max),(jicjifjifjifjifjifjif三角蛋糕三角蛋糕 一塊邊長為一塊邊長為n的正三角形的大蛋糕，一些被老鼠的正三角形的大蛋糕，一些被老鼠咬壞了，如以下圖黑色部分。咬壞了，如以下圖黑色部分。 現(xiàn)想把該蛋糕切出一塊最大的沒被老鼠咬壞正三現(xiàn)想把該蛋糕切出一塊最大的沒被老鼠咬壞正三角形的蛋糕；角形的蛋糕； 求切出的最大的三角形面積求切出的最大的三角形面積 n100。向上的三角形，向上的三角形， 設(shè)頂點(diǎn)坐標(biāo)為設(shè)

17、頂點(diǎn)坐標(biāo)為i,j的三角形最大高度為的三角形最大高度為Fi,j 顯然：顯然： Fi,j=MINFi-1,j-1,Fi-1,j+1 +1， 當(dāng)當(dāng)Ci-1,j=-，表示這個三角形沒被老鼠咬壞。，表示這個三角形沒被老鼠咬壞。向下的三角形 設(shè)頂點(diǎn)坐標(biāo)為設(shè)頂點(diǎn)坐標(biāo)為i,j的三角形最大高度為的三角形最大高度為Gi,j 顯然：顯然： Gi,j=MINGi+1,j-1,Gi+1,j+1 +1， 當(dāng)當(dāng)Ci+1,j=-，表示這個三角形沒被老鼠咬壞。，表示這個三角形沒被老鼠咬壞。分析 分別求分別求Fi,j和和Gi,j 1=i=n,1=j=2n-1 因此，時間復(fù)雜度因此，時間復(fù)雜度ON2 答案為高度的平方，證明如下：答

18、案為高度的平方，證明如下： 假設(shè)最大高度為假設(shè)最大高度為W 那么三角形個數(shù)為那么三角形個數(shù)為+2W-1=W2主程序for i:=1 to n do倒三角情況倒三角情況 for j:=i to 2*n-i do if ci,j=-andi mod 2=j mod 2 then假如該位置沒被吃，而且必假如該位置沒被吃，而且必須是頭朝下的三角須是頭朝下的三角 begin if ci-1,j- then fi,j:=1 else fi,j:=minfi-1,j-1,fi-1,j+1+1;是否可以從上面的位置轉(zhuǎn)移過來是否可以從上面的位置轉(zhuǎn)移過來堆成更大的三角形堆成更大的三角形 if fi,jans then ans:=fi,j; end;正三角情況程序與上類似正三角情況程序與上類似總結(jié)總結(jié) 規(guī)那么類動態(tài)規(guī)劃有一個共性，那就是在