DP-坐標(biāo)規(guī)則型動(dòng)態(tài)規(guī)劃.pptVIP

坐標(biāo)規(guī)則型動(dòng)態(tài)規(guī)劃,長沙市雅禮中學(xué) 朱全民,Robots,在一個(gè)n*m的棋盤內(nèi)，一些格子里有垃圾要拾撿?，F(xiàn)在有一個(gè)能撿垃圾的機(jī)器人從左上格子里出發(fā)，每次只能向右或者向下走。每次他到達(dá)一個(gè)點(diǎn)，就會(huì)自動(dòng)把這個(gè)點(diǎn)內(nèi)的垃圾拾掉。 問：最多能拾多少垃圾。在最多的情況下，有多少種拾垃圾方案？ 數(shù)據(jù)范圍:n=100,m=100,樣例分析,最多能拾5塊。有4種方法。,分析(1),因?yàn)闄C(jī)器人只能向右或者向下走。符合無后效性原則。于是考慮動(dòng)態(tài)規(guī)劃。 設(shè)F(i,j)表示從(1,1)點(diǎn)開始走到(i,j)的時(shí)候，最多撿了多少垃圾。 F(i,j)=Maxf(i-1,j),f(i,j-1)+ci,j 其中Ci,j=1表示(i,j)點(diǎn)有垃圾。Ci,j=0表示沒有 1=i=n,1=j=m，決策2種 時(shí)間復(fù)雜度為O(n*m),分析(2),設(shè)Gi,j表示在fi,j最大的時(shí)候，有多少種方案。 撿到f(i,j)的垃圾只能從兩個(gè)方向來走，方案數(shù)累加即可。因此， g(i,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 時(shí)間復(fù)雜度O(n*m),矩陣取數(shù)游戲 （NOIP2007）,對于一個(gè)給定的n*m的矩陣，矩陣中的每個(gè)元素aij為非負(fù)整數(shù)。游戲規(guī)則如下： 1. 每次取數(shù)時(shí)須從每行各取走一個(gè)元素，共n個(gè)。 m次后取完矩陣所有的元素； 2. 每次取走的各個(gè)元素只能是該元素所在行的行首或行尾； 3. 每次取數(shù)都有一個(gè)得分值，為每行取數(shù)的得分之和；每行取數(shù)的得分 = 被取走的元素值*2i，其中i表示第i次取數(shù)（從1開始編號）； 4. 游戲結(jié)束總得分為m次取數(shù)得分之和。 求出取數(shù)后的最大得分。,樣例,輸入 2 3 1 2 3 3 4 2 輸出 82 第1次：第一行取行首元素，第二行取行尾元素，本次的氛圍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=56 1*21+2*22+3*23= 2*21+3*22+4*23,分析,首先，n行求值可以獨(dú)立考慮！ 設(shè)fi,j表示區(qū)間i-j的最優(yōu)值 fi,j=maxfi+1,j+w*ai , fi,j-1+w*aj 其中w=w+w,即w*2 需要做若干次高精度加法和乘法。 直到求出，maxfi,i+w*ai，i=1m為止。,傳紙條(NOIP2008),小淵坐在矩陣的左上角，坐標(biāo)(1,1)，小軒坐在矩陣的右下角，坐標(biāo)(m,n)。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。 班里每個(gè)同學(xué)都可以幫他們傳遞，但只會(huì)幫他們一次。 每個(gè)同學(xué)愿意幫忙的好感度有高有低，可以用一個(gè)0-100的自然數(shù)來表示，數(shù)越大表示越好心。 小淵和小軒希望盡可能找好心程度高的同學(xué)來幫忙傳紙條，即找到來回兩條傳遞路徑，使得這兩條路徑上同學(xué)的好心程度只和最大?，F(xiàn)在，請你幫助小淵和小軒找到這樣的兩條路徑。 1=m,n=50,貪心,很容易想到一個(gè)算法： 求出1個(gè)紙條從（1，1）到（M,N）的路線最大值. 刪除路徑上的點(diǎn)值 再求出1個(gè)紙條從（M,N） 到（1，1）的路線最大值. 統(tǒng)計(jì)兩次和 上述算法很容易找出反例，如下圖。 第1次找最優(yōu)值傳遞后，導(dǎo)致第2次無法傳遞。,分析,貪心算法錯(cuò)誤，因此我們需要同時(shí)考慮兩個(gè)紙條的傳遞。 由于小淵和小軒的路徑可逆，因此，盡管出發(fā)點(diǎn)不同，但都可以看成同時(shí)從(1,1)出發(fā)到達(dá)(M,N)點(diǎn)。 設(shè)f(i1,j1,i2,j2)表示紙條1到達(dá)(i1,j1)位置，紙條2到達(dá)(i2,j2)位置的最優(yōu)值。則有， 其中 (i1,j1) (i2,j2) 1=i1, i2=M, 1=j1 , j2=N 時(shí)間復(fù)雜度O(N2M2),分析2,另一種思路：每個(gè)紙條都需要走M(jìn)+N步才能達(dá)到目標(biāo)。 因此，設(shè)F(k,i1,i2)表示兩個(gè)紙條都走了K步，第1個(gè)紙條橫坐標(biāo)為i1,第2個(gè)紙條橫坐標(biāo)為i2的最優(yōu)值。 則兩個(gè)紙條的縱坐標(biāo)分別為j1=K-i1, j2=K-i2 ,狀態(tài)轉(zhuǎn)移方程如下： 其中 i1i2 1=i1, i2=M,1=k=N+M 時(shí)間復(fù)雜度O(N+M)*M2),免費(fèi)餡餅,SERKOI最新推出了一種叫做“免費(fèi)餡餅”的游戲。 游戲在一個(gè)舞臺(tái)上進(jìn)行。舞臺(tái)的寬度為W格，天幕的高度為H格，游戲者占一格。開始時(shí)，游戲者站在舞臺(tái)的正中央，手里拿著一個(gè)托盤。 游戲開始后，從舞臺(tái)天幕頂端的格子中不斷出現(xiàn)餡餅并垂直下落。游戲者左右移動(dòng)去接餡餅。游戲者每秒可以向左或右移動(dòng)一格或兩格，也可以站在愿地不動(dòng)。 餡餅有很多種，游戲者事先根據(jù)自己的口味，對各種餡餅依次打了分。同時(shí)在8-308電腦的遙控下，各種餡餅下落的速度也是不一樣的，下落速度以格/秒為單位。當(dāng)餡餅在某一秒末恰好到達(dá)游戲者所在的格子中，游戲者就收集到了這塊餡餅。 寫一個(gè)程序，幫助我們的游戲者收集餡餅，使得收集的餡餅的分?jǐn)?shù)之和最大。,輸入數(shù)據(jù)： 第一行:寬度W（199奇數(shù)）和高度H（1 100整數(shù)） 接下來給出了一塊餡餅信息。由4個(gè)正整數(shù)組成，分別表示了餡餅的 初始下落時(shí)刻、水平位置、下落速度、分值。 游戲開始時(shí)刻為0。從1開始自左向右依次對水平方向的每格編號。 輸出數(shù)據(jù)： 收集到的餡餅最大分?jǐn)?shù)之和。,由上圖可知，盡管下落了4個(gè)餡餅，但只能接到3個(gè)： 第1時(shí)刻可以接到分值為5的餡餅 第2時(shí)刻可以接到分值為3的餡餅 第3時(shí)刻可以接到分值為4的餡餅 因此餡餅的總分值為5+3+4=12,分析,由于餡餅下落的時(shí)間和速度都不同，人只能向左右移動(dòng)，餡餅只能向下移動(dòng)。人和餡餅都同時(shí)移動(dòng)，思考起來比較復(fù)雜，因此我們需要轉(zhuǎn)變思路：,算出每個(gè)時(shí)刻落到最底層的每個(gè)格子有多少分值的餡餅。 如果將餡餅當(dāng)成參照物，則餡餅向下落，可以看成餡餅不動(dòng)，人往上走去摘取餡餅，這樣人每1時(shí)刻都可以走到上一行的5個(gè)格子，如右圖：,動(dòng)態(tài)規(guī)劃,計(jì)算出每個(gè)格子每個(gè)時(shí)刻可能達(dá)到的餡餅分值，填入W*H的天幕表。 其中Ci,j表示天幕的第i行第j列的餡餅分值，即第i時(shí)刻，餡餅落到最底行的餡餅分值。 設(shè)F(i,j)表示人走到第i行j列所取得的餡餅最大分值和，則有， 0=i=T,1=j=W,決策數(shù)為5個(gè) 時(shí)間復(fù)雜度為O(5WT),三角蛋糕,一塊邊長為n的正三角形的大蛋糕，一些被老鼠咬壞了，如下圖黑色部分。 現(xiàn)想把該蛋糕切出一塊最大的沒被老鼠咬壞正三角形的蛋糕； 求切出的最大的三角形面積 n100。,向上的三角形，,設(shè)頂點(diǎn)坐標(biāo)為(i,j)的三角形最大高度為F(i,j) 顯然： F(i,j)=MINF(i-1,j-1),F(i-1,j+1) +1， 當(dāng)Ci-1,j=-，表示這個(gè)三角形沒被老鼠咬壞。,向下的三角形,設(shè)頂點(diǎn)坐標(biāo)為(i,j)的三角形最大高度為G(i,j) 顯然： G(i,j)=MING(i+1,j-1),G(i+1,j+1) +1， 當(dāng)Ci+1,j=-，表示這個(gè)三角形沒被老鼠咬壞。,分析,分別求F(i,j)和G(i,j) 1=i=n,1=j=2n-1 因此，時(shí)間復(fù)雜度O(N2) 答案為高度的平方，證明如下： 假設(shè)最大高度為W 則三角形個(gè)數(shù)為+2W-1=W2,主程序,for i:=1 to n do倒三角情況 for j:=i to 2*n-i do if (ci,j=-)and(i mod 2=j mod 2) then如果該位置沒被吃，而且必須是頭朝下的三角 begin if ci-1,j- then fi,j:=1 else fi,j:=min(fi-1,j-1,fi-1,j+1)+1;是否可以從上面的位置轉(zhuǎn)移過來堆成更大的三角形 if fi,jans then ans:=fi,j; end; 正三角情