3、X[i]個(gè)石子,兩人輪流從中取出石子,規(guī)定每次只能從最左邊或最右邊取出一堆石子,直至石子被全部取出,每個(gè)人所取的石子的總個(gè)數(shù)為個(gè)人的最后得分,得分多的人獲勝。若兩人得分相同,則規(guī)定首先取的人獲勝。如果游戲開(kāi)始時(shí)N為偶數(shù),則對(duì)首先取的人來(lái)說(shuō),存在一種必勝的策略。請(qǐng)你編一個(gè)程序,作為首先取石子的人,尋找一種必勝的策略和計(jì)算機(jī)玩這個(gè)游戲,并讓你自己保持不敗。分析對(duì)于這道題,第一感覺(jué)便是貪心,但貪心存在反例:6,10,4,5。便也只能采用動(dòng)態(tài)規(guī)劃的方法。因?yàn)镹是偶數(shù),所以可將問(wèn)題劃分成N/2個(gè)階段,第i個(gè)階段處理所有相鄰的2i堆石
4、子,相當(dāng)于雙方的第N/2-i+1個(gè)回合。對(duì)每一種狀態(tài),作出取左邊還是取右邊的決策,同時(shí),還需要考慮計(jì)算機(jī)作出決策后,人也要作出相應(yīng)的最佳決策??雌饋?lái)對(duì)于人的兩種決策,似乎有些難以考慮,但只要將人作出最佳決策轉(zhuǎn)化為計(jì)算機(jī)作出較差決策,問(wèn)題便迎刃而解。分析設(shè)b[i,j]表示第i到第j堆石子中,計(jì)算機(jī)最多可獲得的得分,且總堆數(shù)j-i+1為偶數(shù)動(dòng)態(tài)轉(zhuǎn)移方程為:b[i,j]=max(a[i]+min(b[i+2,j],b[i+1,j-1]),a[j]+min(b[i,j-2],b[i+1,j-1]))初始條件為?序列壓縮給出一個(gè)N個(gè)
5、正整數(shù)的序列A=[A1,A2,……,AN],我們可以對(duì)其進(jìn)行壓縮操作.所謂壓縮操作是指:將兩個(gè)相鄰的元素AI和AI+1的差(AI-AI+1)去替代第I個(gè)元素,同時(shí)刪去第I+1個(gè)元素,嚴(yán)格地可以定義如下:CON(A,I)=[A1,,A2,….,AI-1,AI-AI+1,AI+2,…….AN]經(jīng)過(guò)一次序列壓縮之后,我們可以得到一個(gè)N-1個(gè)元素的序列,如此進(jìn)行下去,我們可以僅得到單一的一個(gè)整數(shù)?,F(xiàn)給定一個(gè)正整數(shù)序列和一個(gè)目標(biāo)整數(shù)T,求解并輸出壓縮順序。1〈=N〈=100,-10000〈=T〈=10000示例:con([12,10
6、,4,3,5],2)=[12,6,3,5]con([12,6,3,5],3)=[12,6,-2]con([12,6,-2],2)=[12,8]con([12,8],1)=[4]算法一看了題目最容易想到動(dòng)態(tài)規(guī)劃算法是石子合并問(wèn)題與骨牌問(wèn)題相結(jié)合的方法。其算法如下:設(shè)F[I,J,K]表示將第I個(gè)數(shù)到第J個(gè)數(shù)按規(guī)則壓縮,最后能否壓縮成數(shù)K。不難得出動(dòng)態(tài)轉(zhuǎn)移方程為:F[I,J,K]=Falseor(F[I,M,K1]andF[M+1,J,K1-K])其中I<=M7、RUE如果F[1,N,T]的值為真,該問(wèn)題有解,否則無(wú)解。至于求具體方案,可以用一個(gè)父結(jié)點(diǎn)數(shù)組記下推出F[I,J,K]的M、K1值。也可在最后用一個(gè)反向的動(dòng)態(tài)規(guī)劃找最優(yōu)方案。從上面的動(dòng)態(tài)規(guī)劃方程可以看出,該算法在最壞的情況下時(shí)間復(fù)雜度將接近于10000^2*100^3,由于最后要輸出最優(yōu)方案,不可用滾動(dòng)數(shù)組,因此它的空間復(fù)雜度為o(10000*100^2),無(wú)論從時(shí)間還是空間上來(lái)看,該算法都不適合于該問(wèn)題。算法二只要仔細(xì)分析問(wèn)題不難看出,該問(wèn)題是要我們?cè)谳斎氲牡?至第N-1個(gè)數(shù)前面加減號(hào),并且在這個(gè)式子中添入N-1個(gè)括號(hào),
8、使得式子最終的計(jì)算結(jié)果為給定的數(shù)T。我們不妨將所有的括號(hào)都拆掉,最后該式子將會(huì)成為一個(gè)沒(méi)有括號(hào)的加減式。注意:只要稍加分析即可發(fā)現(xiàn),該加減式的第二個(gè)數(shù)前面肯定是減號(hào)。反過(guò)來(lái)考慮,如果一個(gè)加減式的第二個(gè)數(shù)前面為減號(hào),其余的數(shù)前面為“+”號(hào)或“-”號(hào)(第一個(gè)前面沒(méi)有符號(hào)),那么該式子能否變?yōu)橐粋€(gè)由N-1個(gè)括