動(dòng)態(tài)規(guī)劃第7講

免費(fèi)餡餅SERKOI最新推出了一種叫做“免費(fèi)餡餅”的游戲。游戲在一個(gè)舞臺(tái)上進(jìn)行。舞臺(tái)的寬度為W格，天幕的高度為H格，游戲者占一格。開(kāi)始時(shí)，游戲者站在舞臺(tái)的正中央，手里拿著一個(gè)托盤(pán)。游戲開(kāi)始后，從舞臺(tái)天幕頂端的格子中不斷出現(xiàn)餡餅并垂直下落。游戲者左右移動(dòng)去接餡餅。游戲者每秒可以向左或右移動(dòng)一格或兩格，也可以站在愿地不動(dòng)。餡餅有很多種，游戲者事先根據(jù)自己的口味，對(duì)各種餡餅依次打了分。同時(shí)在8-308電腦的遙控下，各種餡餅下落的速度也是不一樣的，下落速度以格/秒為單位。當(dāng)餡餅在某一秒末恰好到達(dá)游戲者所在的格子中，游戲者就收集到了這塊餡餅。寫(xiě)一個(gè)程序，幫助我們的游戲者收集餡餅，使得收集的餡餅的分?jǐn)?shù)之和最大。免費(fèi)餡餅輸入數(shù)據(jù)：輸入文件的第一行是用空格分開(kāi)的兩個(gè)正整數(shù)，分別給出了舞臺(tái)的寬度W（1~99之間的奇數(shù)）和高度H（1~100之間的整數(shù)）。接下來(lái)依餡餅的初始下落時(shí)間順序給出了一塊餡餅信息。由四個(gè)正整數(shù)組成，分別表示了餡餅的初始下落時(shí)刻（0~1000秒），水平位置、下落速度（1~100）以及分值。游戲開(kāi)始時(shí)刻為0。從1開(kāi)始自左向右依次對(duì)水平方向的每格編號(hào)。輸出數(shù)據(jù)：輸出文件的第一行給出了一個(gè)正整數(shù)，表示你的程序所收集到的最大分?jǐn)?shù)之和。分析我們將問(wèn)題中的餡餅信息用一個(gè)表格存儲(chǔ)。表格的第I行第J列表示的是游戲者在第I秒到達(dá)第J列所能取得的分值。那么問(wèn)題便變成了一個(gè)類(lèi)似數(shù)字三角形的問(wèn)題：從表格的第一行開(kāi)始往下走，每次只能向左或右移動(dòng)一格或兩格，或不移動(dòng)走到下一行。怎樣走才能得到最大的分值。因此，我們很容易想到用動(dòng)態(tài)規(guī)劃求解。F[I,J]表示游戲進(jìn)行到第I秒，這時(shí)游戲者站在第J列時(shí)所能得到的最大分值。那么動(dòng)態(tài)轉(zhuǎn)移方程為：F[I,J]=Max{F[I-1,K]}+餡餅的分值(J-2<=K<=J+2)Robots

在一個(gè)n*m的棋盤(pán)內(nèi)，一些格子里有垃圾要拾撿。現(xiàn)在有一個(gè)能撿垃圾的機(jī)器人從左上格子里出發(fā)，每次只能向右或者向下走。每次他到達(dá)一個(gè)點(diǎn)，就會(huì)自動(dòng)把這個(gè)點(diǎn)內(nèi)的垃圾拾掉。問(wèn)：最多能拾多少垃圾。在最多的情況下，有多少種方案？請(qǐng)舉出一種方案來(lái)。數(shù)據(jù)范圍:n<=100,m<=100舉例最多能拾5塊。有4種方法。分析：因?yàn)橹荒芟蛴一蛘呦蛳伦?。也就是說(shuō)不能走回頭路。于是考慮動(dòng)態(tài)規(guī)劃。設(shè)F[i,j]表示從(1,1)點(diǎn)開(kāi)始走到(i,j)的時(shí)候，最多撿了多少垃圾。G[i,j]表示在f[i,j]最大的時(shí)候，有多少種方案。C[i,j]=1表示(i,j)點(diǎn)有垃圾。C[i,j]=0表示沒(méi)有。狀態(tài)轉(zhuǎn)移方程根據(jù)(i,j)只能從(i-1,j)或者(i,j-1)走過(guò)來(lái)。于是f[i,j]=Max{f[i-1,j],f[i,j-1]}+c[i,j].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?？偨Y(jié)于是我們得到第1，2問(wèn)的答案。對(duì)于第3問(wèn)，我們只要簡(jiǎn)單得在動(dòng)態(tài)規(guī)劃的時(shí)候記錄一個(gè)決策即從哪個(gè)方向走過(guò)來(lái)的就可以了。時(shí)間復(fù)雜度O(nm)。總結(jié)巧妙的轉(zhuǎn)化關(guān)系是這道題目的關(guān)鍵。時(shí)間復(fù)雜度:O(最大匹配的時(shí)間復(fù)雜度)=O(tot^3)Tot為垃圾點(diǎn)的個(gè)數(shù)。分析K=2或者k=3的時(shí)候，可以考慮使用動(dòng)態(tài)規(guī)劃。F[x1,x2..xk,y1,y2..yk]表示當(dāng)前這k個(gè)人為于x1..xk這3個(gè)位置，且x1..xk左上沒(méi)有垃圾了。這k個(gè)人分別撿了y1..yk個(gè)垃圾。K更大的時(shí)候，可以考慮采用搜索+剪枝。因?yàn)閱?wèn)題的方案很多。所以有比較好的效果。瑰麗華爾茲(adv1900)

一個(gè)N行M列的矩陣，矩陣中有些位置為空地，有些位置為障礙?，F(xiàn)在每一個(gè)時(shí)刻，你可以選擇原地不動(dòng)或沿著指定的方向移動(dòng)一格，但是不可以移出這個(gè)矩陣或撞到障礙?！爸付ǚ较颉睘镵個(gè)連續(xù)的區(qū)間[Si,Ti,Di],表示在[Si,Ti]的區(qū)間的方向?yàn)镈i.Di=1,2,3,4分別表示上下左右?，F(xiàn)在求最多可以滑行多少步。50%的數(shù)據(jù)中，1≤N,M≤200，T≤200；100%的數(shù)據(jù)中，1≤N,M≤200，K≤200，T≤40000。分析看到這個(gè)模型，很容易列出如下的DP方程：設(shè)f(i,j,k)表示前i個(gè)區(qū)間滑行完后，停留在(j,k)最多滑行了多少步。f(i,j,k)=max{f(i-1,j+s,k)+s}Di=1f(i,j,k)=max{f(i-1,j-s,k)+s}Di=2f(i,j,k)=max{f(i-1,j,k+s)+s}Di=3f(i,j,k)=max{f(i-1,j,k-s)+s}Di=4對(duì)于第一方程,s需要滿足：(t,k)全部為空格，j<=t<=j+sj+s<=Ns<=Ti-Si其余三個(gè)方程同理。優(yōu)化這個(gè)Dp方程的時(shí)間復(fù)雜度為O(KN^2M),顯然是不滿足題目要求的。因此我們需要對(duì)這個(gè)方程進(jìn)行優(yōu)化，我們不妨以Di=1為例，其他的同理。f(i,j,k)=max{f(i-1,j+s,k)+s}枚舉i,k.設(shè)a(j)=f(i-1,j,k)+j,則f(i,j,k)=max{a(t)-j}=max{a(t)}-j,且t需要滿足(j,k)..(t..k)全部為空格,0<=t-j<=Ti-Si因此在枚舉j的過(guò)程中，我們同時(shí)需要維護(hù)當(dāng)前的決策集合。我們建立一個(gè)隊(duì)列Pi,滿足

P1>P2>P3>P4…>Pva(P1)>a(P2)>a(P3)>a(P4)>…>a(Pv)

因?yàn)閷?duì)于j<k,a(j)>=a(k),k決策顯然就沒(méi)有意義了。維護(hù)當(dāng)前隊(duì)列：若(j,k)為空格：將j決策插入隊(duì)列：從隊(duì)尾開(kāi)始往前將所有a(Pi)<=a(j)的Pi值從隊(duì)列中刪除，將j插入隊(duì)尾，這樣依舊保持了隊(duì)列的單調(diào)性。將不滿足條件的元素刪除：當(dāng)隊(duì)首的決策P1-j>Ti-Si,則將隊(duì)首刪除。F(i,j,k)=a(P1)-j

若(j,k)為障礙，則大于等于j的所有的決策全部失效，因此此時(shí)需要將整個(gè)隊(duì)列清空。這樣用隊(duì)列優(yōu)化使得每一次的轉(zhuǎn)移由O(N)變成了O(1).因此總的時(shí)間復(fù)雜度變成了O(KMN),已經(jīng)完全可以勝任題目的要求了。

矩陣取數(shù)游戲（NOIP2007）對(duì)于一個(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開(kāi)始編號(hào)）；4.游戲結(jié)束總得分為m次取數(shù)得分之和。求出取數(shù)后的最大得分。樣例輸入23

124

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<=n,m<=30，答案不超過(guò)1016100%的數(shù)據(jù)滿足：1<=n,m<