動(dòng)態(tài)規(guī)劃入門(2)

1、動(dòng)態(tài)規(guī)劃入門（2）問(wèn)題引入： X星球特別講究秩序，所有道路都是單行線。一個(gè)甲殼蟲車隊(duì)，共n輛車，按照編號(hào)先后發(fā)車，夾在其它車流中，緩緩前行。 路邊有個(gè)死胡同，只能容一輛車通過(guò)，是臨時(shí)的檢查站，如圖【p1.png】所示。 X星球太死板，要求每輛路過(guò)的車必須進(jìn)入檢查站，也可能不檢查就放行，也可能仔細(xì)檢查。 如果車輛進(jìn)入檢查站和離開的次序可以任意交錯(cuò)。那么，該車隊(duì)再次上路后，可能的次序有多少種？ dp(i,j)=dp(i-1,j+1)+dp(i,j-1)問(wèn)題引入（2）:ABC每個(gè)字母有每個(gè)字母有n個(gè)，求滿足要求的排列的個(gè)數(shù)：在該個(gè)，求滿足要求的排列的個(gè)數(shù)：在該排列的任意前綴中滿足排列的任意前綴中滿足

2、 A的個(gè)數(shù)不少于的個(gè)數(shù)不少于B的的個(gè)數(shù)個(gè)數(shù), B的個(gè)的個(gè)數(shù)數(shù)不不少于少于C的個(gè)數(shù)。的個(gè)數(shù)。dpijk = dpi-1jk+dpij-1k+dpijk-1，并且，并且i=j=k在一個(gè)凸多邊形中，通過(guò)若干條互不相交的對(duì)角線，把這個(gè)多邊形劃分成了若干個(gè)三角形。任務(wù)是鍵盤上輸入凸多邊形的邊數(shù)n，求不同劃分的方案數(shù)f（n）。比如當(dāng)n=6時(shí)，f（6）=14。h(n)= h(0)*h(n-1)+h(1)*h(n-2) + . + h(n-1)h(0) (n=2)算出1題和3題的部分答案 第一題 125134213242914301679658786。 第三題1251342132429143016796587

3、86?？ㄌ靥m數(shù)狀態(tài)轉(zhuǎn)移的相關(guān)內(nèi)容 問(wèn)題 hdu2191悼念悼念512汶川大地震遇難同胞汶川大地震遇難同胞珍惜現(xiàn)在，感恩生活珍惜現(xiàn)在，感恩生活為了挽救災(zāi)區(qū)同胞的生命，心系災(zāi)區(qū)同胞的你準(zhǔn)備自己采購(gòu)一些糧食支援災(zāi)區(qū)，現(xiàn)在假設(shè)你一共有資金n元，而市場(chǎng)有m種大米，每種大米都是袋裝產(chǎn)品，其價(jià)格不等，并且只能整袋購(gòu)買。請(qǐng)問(wèn)：你用有限的資金最多能采購(gòu)多少公斤糧食呢？Input輸入數(shù)據(jù)首先包含一個(gè)正整數(shù)C，表示有C組測(cè)試用例，每組測(cè)試用例的第一行是兩個(gè)整數(shù)n和m(1=n=100, 1=m=100),分別表示經(jīng)費(fèi)的金額和大米的種類，然后是m行數(shù)據(jù)，每行包含3個(gè)數(shù)p，h和c(1=p=20,1=h=200,1=c=2

4、0)，分別表示每袋的價(jià)格、每袋的重量以及對(duì)應(yīng)種類大米的袋數(shù)。Output對(duì)于每組測(cè)試數(shù)據(jù)，請(qǐng)輸出能夠購(gòu)買大米的最多重量，你可以假設(shè)經(jīng)費(fèi)買不光所有的大米，并且經(jīng)費(fèi)你可以不用完。每個(gè)實(shí)例的輸出占一行。兩種狀態(tài)轉(zhuǎn)移方程 dpj=max(dpj,dpj-pi+vi); dpj=max(dpj,dpj-pi*k+k*vi);dpi數(shù)組的意義為容量為i時(shí)的最大價(jià)值#include #include #include using namespace std;int main() int n,m,dp105,kase,num105,v105,p105; scanf(%d,&kase); while(

5、kase-) scanf(%d%d,&n,&m); for(int i=0; im; i+) scanf(%d%d%d,&pi,&vi,&numi); memset(dp,0,sizeof(dp); for(int i=0; i0; j-) for(int k=1; k=0) dpj=max(dpj,dpj-pi*k+k*vi); printf(%dn,dpn); return 0;#include #include #include using namespace std;int main() int n,m,dp105,kase,num105,v10

6、5,p105; scanf(%d,&kase); while( kase-) scanf(%d%d,&n,&m); for(int i=0; im; i+) scanf(%d%d%d,&pi,&vi,&numi); memset(dp,0,sizeof(dp); for(int i=0; im; i+) for(int k=1; k0; j-) if(j-pi=0) dpj=max(dpj,dpj-pi+vi); printf(%dn,dpn); return 0;Floyd算法 void Floyd() int i,j,k; for(k=1;k

7、=n;k+) for(i=1;i=n;i+) for(j=1;j=n;j+) if(distik+distkjdistij) distij=distik+distkj; 那么，就有：1.若最短路徑經(jīng)過(guò)節(jié)點(diǎn)vk，則D(i,j,k) = D(i,k,k-1) + D(k,j,k-1)； 2.若最短路徑不經(jīng)過(guò)節(jié)點(diǎn)vk，則D(i,j,k) = D(i,j,k-1)。所以，求的vi到vj的最短路徑可表示為：D(i,j,k) = min（D(i,k,k-1) + D(k,j,k-1), D(i,j,k-1)）。最短距離有三種情況：、兩點(diǎn)的直達(dá)距離最短。（如下圖）、兩點(diǎn)間只通過(guò)一個(gè)中間點(diǎn)而距離最短。（圖）、

8、兩點(diǎn)間用通過(guò)兩各以上的頂點(diǎn)而距離最短。（圖）對(duì)于第二種情況：弗洛伊德算法的基本操作就是對(duì)于每一對(duì)頂點(diǎn)，遍歷所有其它頂點(diǎn)，看看可否通過(guò)這一個(gè)頂點(diǎn)讓這對(duì)頂點(diǎn)距離更短，也就是遍歷了圖中所有的三角形（算法中對(duì)同一個(gè)三角形掃描了九次，原則上只用掃描三次即可，但要加入判斷，效率更低）。對(duì)于第三種情況：如下圖的五邊形，可先找一點(diǎn)（比如x，使=2），就變成了四邊形問(wèn)題，再找一點(diǎn)（比如y,使=2），可變成三角形問(wèn)題了（v,u,w），也就變成第二種情況了，由此對(duì)于n邊形也可以一步步轉(zhuǎn)化成四邊形三角形問(wèn)題。（這里面不用擔(dān)心哪個(gè)點(diǎn)要先找哪個(gè)點(diǎn)要后找，因?yàn)檎伊巳我粋€(gè)點(diǎn)都可以使其變成（n1）邊形的問(wèn)題）。課后練習(xí)n個(gè)人（編號(hào)0(n-1)，從0開始報(bào)數(shù)，報(bào)到(m-1)的退出，剩下的人繼續(xù)從0開始報(bào)數(shù)。求勝利者的編號(hào)。int Josephus