資源描述：
《NOI導(dǎo)刊坐標(biāo)規(guī)則型動(dòng)態(tài)規(guī)劃.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。
1、反對(duì)文檔高定價(jià)！坐標(biāo)規(guī)則型動(dòng)態(tài)規(guī)劃長(zhǎng)沙市雅禮中學(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)的垃圾拾掉。問(wèn)：最多能拾多少垃圾。在最多的情況下，有多少種拾垃圾方案？數(shù)據(jù)范圍:n<=100,m<=100樣例分析最多能拾5塊。有4種方法。分析(1)因?yàn)闄C(jī)器人只能向右或者向下走。符合無(wú)后效性原則。于是考慮動(dòng)態(tài)規(guī)劃。設(shè)F(i,j)表示從(1,1)點(diǎn)開始走到(i,j)的時(shí)候，最多撿了多少垃圾。F(i,j)=Max{f(i-1,j),f(i,j-1)}+c[i,j]其中
2、C[i,j]=1表示(i,j)點(diǎn)有垃圾。C[i,j]=0表示沒(méi)有1<=i<=n,1<=j<=m，決策2種時(shí)間復(fù)雜度為O(n*m)分析(2)設(shè)G[i,j]表示在f[i,j]最大的時(shí)候，有多少種方案。撿到f(i,j)的垃圾只能從兩個(gè)方向來(lái)走，方案數(shù)累加即可。因此，g(i,j)=g[i-1,j]*k+g[i,j-1]*L如果f[i-1,j]+c[i,j]=f[i,j]，則K=1否則K=0。如果f[i,j-1]+c[i,j]=f[i,j]，則L=1否則L=0時(shí)間復(fù)雜度O(n*m)矩陣取數(shù)游戲（NOIP2007）對(duì)于一個(gè)給定的n*m的矩陣，矩陣中的每個(gè)元素aij為非負(fù)整數(shù)。游戲規(guī)則如下：
3、1.每次取數(shù)時(shí)須從每行各取走一個(gè)元素，共n個(gè)。m次后取完矩陣所有的元素；2.每次取走的各個(gè)元素只能是該元素所在行的行首或行尾；3.每次取數(shù)都有一個(gè)得分值，為每行取數(shù)的得分之和；每行取數(shù)的得分=被取走的元素值*2i，其中i表示第i次取數(shù)（從1開始編號(hào)）；4.游戲結(jié)束總得分為m次取數(shù)得分之和。求出取數(shù)后的最大得分。樣例輸入23 123 342輸出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<=
4、n,m<=30，答案不超過(guò)1016100%的數(shù)據(jù)滿足：1<=n,m<=80，0<=aij<=10001*21+2*21=62*22+3*22=203*23+4*23=561*21+2*22+3*23=2*21+3*22+4*23分析首先，n行求值可以獨(dú)立考慮！設(shè)f[i,j]表示區(qū)間i-j的最優(yōu)值f[i,j]=max{f[i+1,j]+w*a[i]?,?f[i,j-1]+w*a[j]}其中w=w+w,即w*2需要做若干次高精度加法和乘法。直到求出，max{f[i,i]+w*a[i]，i=1..m}為止。傳紙條(NOIP2008)小淵坐在矩陣的左上角，坐標(biāo)(1,1)，小軒坐在矩陣的
5、右下角，坐標(biāo)(m,n)。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。班里每個(gè)同學(xué)都可以幫他們傳遞，但只會(huì)幫他們一次。每個(gè)同學(xué)愿意幫忙的好感度有高有低，可以用一個(gè)0-100的自然數(shù)來(lái)表示，數(shù)越大表示越好心。小淵和小軒希望盡可能找好心程度高的同學(xué)來(lái)幫忙傳紙條，即找到來(lái)回兩條傳遞路徑，使得這兩條路徑上同學(xué)的好心程度只和最大?，F(xiàn)在，請(qǐng)你幫助小淵和小軒找到這樣的兩條路徑。1<=m,n<=50貪心很容易想到一個(gè)算法：求出1個(gè)紙條從（1，1）到（M,N）的路線最大值.刪除路徑上的點(diǎn)值再求出1個(gè)紙條從（M,N）到（1，1）的路線最大值.統(tǒng)計(jì)兩次和上述
6、算法很容易找出反例，如下圖。第1次找最優(yōu)值傳遞后，導(dǎo)致第2次無(wú)法傳遞。分析貪心算法錯(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)
7、為i2的最優(yōu)值。則兩個(gè)紙條的縱坐標(biāo)分別為j1=K-i1,j2=K-i2,狀態(tài)轉(zhuǎn)移方程如下：其中i1<>i21<=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)一格或兩格，也可以站在愿地不
