動(dòng)態(tài)規(guī)劃上機(jī)習(xí)題

1、動(dòng)態(tài)規(guī)劃上機(jī)習(xí)題,臧家瑞,地板覆蓋（簡(jiǎn)）,用2*1的地板塊覆蓋3*n的地板有多少種方案？ 如下圖是一個(gè)覆蓋的例子：,,。。。。。。上下翻轉(zhuǎn)也可以——乘以2,動(dòng)態(tài)轉(zhuǎn)移方程,石子游戲,現(xiàn)有4堆石子,兩個(gè)人輪流取石子,他們有n種可能的取法,取法表示從第1堆取A1個(gè)石子,從第2堆中取B1個(gè),第3堆取C1個(gè),第4堆取D1個(gè).如果取的時(shí)候某一堆的石子數(shù)比所要取的石子數(shù)要少,則這種取法是不可行的.取到最后沒有可行取法的人就算輸了. 現(xiàn)給出4堆

2、石子的石子數(shù)目以及n種取法,請(qǐng)問如果兩個(gè)人都采用最優(yōu)取法,先取的人是贏還是輸.,數(shù)據(jù)結(jié)構(gòu),每一種石子數(shù)為一個(gè)狀態(tài)state，每個(gè)狀態(tài)都記錄先手回合的先手輸贏offen和后手回合的先手輸贏defen.struct state {bool offen;//先手回合時(shí)，1：先手贏， 0：先手輸boot defen;//后手回合時(shí)，1：先手贏， 0：先手輸}struct state st[31][31][31][31]；//所

3、有狀態(tài)記錄n種取法的數(shù)組struct remove {int a, b, c, d;} rm[10];,動(dòng)態(tài)轉(zhuǎn)移方程,初始化,多邊形游戲,多邊形游戲是一種在一個(gè)具有n個(gè)頂點(diǎn)的多邊形上進(jìn)行的游戲。如圖1是一個(gè)n=4對(duì)應(yīng)多邊形，每個(gè)頂點(diǎn)上都有一個(gè)整數(shù)，每條邊都有一個(gè)運(yùn)算符+或者*，所有邊按從1到n進(jìn)行編號(hào)。,多邊形游戲,游戲都首先移除一條邊，接下來可以進(jìn)行如下操作：選擇一條邊E和與之相關(guān)聯(lián)的點(diǎn)V1和V2，用一個(gè)新的點(diǎn)替換它們，

4、新點(diǎn)上的整數(shù)為V1,V2上的整數(shù)用E上的操作符運(yùn)算后的結(jié)果。 沒有邊時(shí)游戲結(jié)束，游戲得分就是最后剩下的那個(gè)頂點(diǎn)上的整數(shù)。 對(duì)于圖1中的多邊形，如果游戲者首先去掉3，然后依次去掉1、4、2，最后得分將是0。,多邊形游戲,多邊形游戲,關(guān)于輸入 輸入第一行是一個(gè)正整數(shù)n(3<=n<=50)，表示多邊形的邊數(shù)。接下來一行是這個(gè)多邊形的描述，包含n條邊和n個(gè)頂點(diǎn)，加號(hào)邊用t表示，乘號(hào)邊用x表示，頂點(diǎn)用頂點(diǎn)上標(biāo)的整數(shù)表示，輸入按

5、照邊的編號(hào)從1到n的順序給出。 關(guān)于輸出 第一行輸出可能得到的最高分。 第二行輸出一些邊的列表，只有第一步移除的邊在這個(gè)列表中才可能得到最高分。每條邊都用這個(gè)邊上的編號(hào)表示，列表必須是升序的。,狀態(tài),max[i][j]表示順時(shí)針方向從邊i的終點(diǎn)連續(xù)j條邊進(jìn)行計(jì)算所能得到的最高分min[i][j]表示順時(shí)針方向從邊i的終點(diǎn)連續(xù)j條邊進(jìn)行計(jì)算所能得到的最低分由于環(huán)狀結(jié)構(gòu)，第n條邊及第0條邊edge[i]表示邊i上的運(yùn)算符wei

6、ght[i]表示邊i的終點(diǎn)的權(quán)值問題所求即為max[i][n-1],(i=0,1,2,…n-1) 中的最大值,動(dòng)態(tài)轉(zhuǎn)移方程,基因串,基因串是由一串有限長(zhǎng)度的基因所組成的，其中每一個(gè)基因都可以用26個(gè)英文大寫字母中的一個(gè)來表示，不同的字母表示不同的基因類型。一個(gè)單獨(dú)的基因可以生長(zhǎng)成為一對(duì)新的基因，而可能成長(zhǎng)的規(guī)則是通過一個(gè)有限的成長(zhǎng)規(guī)則集所決定的。每一個(gè)成長(zhǎng)的規(guī)則可以用三個(gè)大寫英文字母A1A2A3來描述，這個(gè)規(guī)則的意思是基因A1可以成長(zhǎng)

7、為一對(duì)基因A2A3。 用大寫字母S來表示一類稱作超級(jí)基因的基因，因?yàn)槊恳粋€(gè)基因串都是由一串超級(jí)基因根據(jù)給出的規(guī)則所成長(zhǎng)出來的。 請(qǐng)寫一個(gè)程序，讀入有限條成長(zhǎng)的規(guī)則和一些我們想要得到的基因串，然后對(duì)于每個(gè)基因串，判斷它是否可以由一個(gè)有限長(zhǎng)度的超級(jí)基因串成長(zhǎng)得出。如果可以，給出可成長(zhǎng)為該基因串的最短超級(jí)基因串的長(zhǎng)度。,準(zhǔn)備,集合reduc[i][j]表示從第i個(gè)基因開始長(zhǎng)度為j的基因串可以歸約成的單個(gè)基因的集合。Gstr為目標(biāo)基因串

8、reduc[i][1]={Gstr[i]};reduc[i][j] = U{reduc[i][k] · reduc[i+k][j-k]} ，如果reduc[i][k]中存在基因A，reduc[i+k][j-k]中存在基因B，滿足C->AB則C ? U{reduc[i][k] · reduc[i+k][j-k]} 全集E＝{A，B，C，…，Z}，可以用一個(gè)整型變量作集合的bitmap,動(dòng)態(tài)歸劃,short[i

9、][j]表示從第i個(gè)基因開始長(zhǎng)度為j的基因串最少可以歸約成的超級(jí)基因數(shù)動(dòng)態(tài)轉(zhuǎn)移方程short[i][j] = MIN { 1 + short[i+k][j-k]}，k滿足reduc[i][k]中含有S，k=1,2,….j初始化short[i][j] = +∞，short[i][0]=0,象棋比賽,你需要從你的棋牌協(xié)會(huì)中選出30人參加一場(chǎng)團(tuán)隊(duì)邀請(qǐng)賽,比賽共30場(chǎng),15人先手持紅,另15人后手持黑.每個(gè)人先手和后手的能力值有所不

10、同,現(xiàn)在你需要從你的協(xié)會(huì)里選出這30人,使得其中15人持紅的能力值與另外15人持黑的能力值的總和盡可能大.,動(dòng)態(tài)轉(zhuǎn)移方程,ability[i][j][k]：在i個(gè)人中選j個(gè)人執(zhí)紅，k個(gè)人執(zhí)黑所得能力值總值的最大值，初始化為0.,地板覆蓋,用1*2的地板磚覆蓋n*m的地板有多少種方案呢?,,如果n與m全是奇數(shù)，0種方案每一行用一個(gè)bitvector表示，從上一行繼承下來一個(gè)格子被覆蓋，則該位標(biāo)記為1,否則標(biāo)記為0，如下圖的bitvect

11、or即為0010011011,,從一行到下一行可以表示為狀態(tài)的轉(zhuǎn)化，如0010011011可以達(dá)到1100000100（如圖），還可以達(dá)到0000000100，0001100100，1101100100,,用整型變量來表示這些bitvector狀態(tài)。判斷狀態(tài)i是否可達(dá)狀態(tài)j，狀態(tài)1111…1記為f,i?(~i)&f若j&((~i)&f)==j，且(~i)&f - j中所有的1都可以按相臨位置兩兩綁定