取數(shù)模型與DP

1、取數(shù)模型與DP1、數(shù)字三角形每行取一個(下面的位置是上面的鄰居)，從上往下，求最大和。樣例：輸入N=5,下面是5行數(shù)字：738810274445265DP方程：ai,j:=maxai+1,j,ai+1,j+1+ai,j(l<=i,j<=n-1)主要程序段：fori:=n-1downto1do從倒數(shù)第二行往上做。Forj:=1toidoIfai+1,j>ai+1,j+1thenai,j:=ai,j+ai+1,jElseai,j:=ai,j+ai+1,j+1;Writeln(a1,1);2、求環(huán)形整數(shù)串的最大連續(xù)和。P1308輸入樣例6-2301-4880輸出樣例82線形DP:可

2、力=max-1+況/,班力,1<j<nansmaxZ>7,1<j<n轉(zhuǎn)化成環(huán)形分兩種情況：1、 如：-2201-481,顯然其最大和連續(xù)子串是201,其和是3。選的是中間的一段，這種情況直接使用上述的線形DP公式。2、樣例：-2301-4880結(jié)果82選的是斷開處的兩端，要當(dāng)成環(huán)處理。怎樣處理第2種情況呢？第2種情況可以找中間連續(xù)一段最小的值，然后拿所有數(shù)的和-最小值DP方法：在上頁DP方程的基礎(chǔ)上，Ans=MAX（線fDP最大值,sum-線TIeDP最小值）;N值很大，如果超過數(shù)組能定義的范圍，可以不用數(shù)組保存這N個數(shù)，而是直接讀一個數(shù)就處理一次。3、求最長不下

3、降序列P1194樣例：輸入14表示14個數(shù)13791638243718441921226315輸出8長度為879161819212263其中一種取法從前往后，每選一個數(shù)，總可以得到此時的最長序列，這一段的最長序列不會因為后面的不同取數(shù)方法而改變，故無后效性。DP方程為:Fi=MAX（F1,，曰1,其中所項的一項必須能與Fi相連接）+1。4、求兩串字符的最長公共子序列輸入樣例ABCBDABBDCABA輸出樣例4BCBA樣例：C4,5因為x4=y5,所以c4,5=c3,4+1C5,4因為x5<>y4,所以c5,4=maxc5,3,c4,4最后輸出C7,6的值。用ci,j記錄序列Xi和Y

4、j的最長公共子序列的長度。Ci,j的值表示：取X列的前i個字母，取y列的前j個字母得到的公共最長子序列的長度。邊界：當(dāng)i=0或j=0時，ci,j=0。ro當(dāng)工=?；?=o時cij=5-L八1+1當(dāng)八）>0且毛=為時max（4,J-1,力-L力）當(dāng)iJ>0且麗=為時fori:=1tolength（x）doforj:=1tolength（y）doifxi=yjthenci,j:=ci-1,j-1+1elseifci-1,j>ci,j-1thenci,j:=ci-1,jelseci,j:=ci,j-1;5、求三串中的最長公共子串。P1338胖男孩varsol:array0.100,

5、0.100,0.100ofstring100;sa,sb,sc:string1la,lb,lc:integer;procedurework;vari,j,k:integer;max:string;beginfori:=1toladoforj:=1tolbdofork:=1to1cdobeginmax:=''so1i,j,k:=''if1ength(so1i-1,j,k)>1ength(max)thenmax:=soli-1,j,k;iflength(soli,j-1,k)>length(max)thenmax:=so1i,j-1,k;if1ength

6、(so1i,j,k-1)>1ength(max)thenmax:=so1i,j,k-1;if1ength(so1i-1,j-1,k)>1ength(max)thenmax:=so1i-1,j-1,k;if1ength(so1i-1,j,k-1)>1ength(max)thenmax:=so1i-1,j,k-1;if1ength(so1i,j-1,k-1)>1ength(max)thenmax:=so1i,j-1,k-1;if(sai=sbj)and(sbj=sck)and(1ength(so1i-1,j-1,k-1+sai)>1ength(max)thenmax:

7、=so1i-1,j-1,k-1+sai;so1i,j,k:=max;end;end;beginread1n(sa);read1n(sb);read1n(sc);1a:=1ength(sa);1b:=1ength(sb);1c:=1ength(sc);work;write1n(1ength(so11a,1b,1c);end.6、機(jī)器分配P1029M個數(shù)N個人取，取不同的數(shù)得到的代價不同，怎樣取，代價最大。32/3個數(shù)，2個人取123個數(shù)的代價123個數(shù)的代價123/第一個人取234/第二個人取輸出：4萬案一：萬案一：萬案二：第一個人取第一個人取第一個人取2個數(shù)，代價3個數(shù)，代價1個數(shù)，代價2,第

8、二個人取1個數(shù)，代價2,總和是431,第二個人取2個數(shù)，總和是4雖然方案很多，但最大代價和是4固定的。用Ai,j保存下面的N行數(shù)據(jù)。Fi,j表示第i個人取j臺的最大價值。能否用前面的狀態(tài)來表示呢？如F2,3表示2個公司分配3臺的最大價值?？梢杂檬裁磥肀硎?F1,0+A2,3F1,1+A2,2F2,3=maxF1,2+A2,1F1,3+A2,0DP方程：Fi,j=maxFi-1,k+Ai,j-k（k取0.m）邊界：F1,i=A1,i（i取1.n）7、P1159乘法游戲?qū)個數(shù)中的2-N個數(shù)排一個順序，每次取一個，將它與相鄰兩數(shù)相乘，求乘積和最大。樣例說明：61015050205取數(shù)順序4123從

9、而得到：50*1*50+50*1*20+20*1*5+1*10*5=3650用Fi,j表示從ai到aj得到的最小值。先算出最小的幾個，每組選3個數(shù)。F1,3=F2,4=F3,5F4,6開始擴(kuò)大范圍，每組選4個數(shù)?？茨懿荒苡们懊娴姆椒ㄟM(jìn)行規(guī)劃。F1,4=F2,5=F3,6=Flr2+F2,4+al2+a4必團(tuán)是最后取的F1,41=效）、F1,3-H73,4+al*afo（a3是最后取的數(shù)）得到DP方程ElLjhMini（i<k<j）18、最小代價子母樹：將N個數(shù)中相鄰的兩數(shù)合并后，變成一個數(shù)，再放到原位置，直到最后變成一個數(shù)，共進(jìn)行N-1次合并，求這N-1次過程中，將每次得到的一個數(shù)

10、的相加，求最小的和。41235+7+10=225+5+10=20用FI,j表示從i到j(luò)的最小代價A、B方案是F1,3+10C方案是F1,2+F3,4+10D、E方案是F2,4+10推導(dǎo)出動態(tài)方程為：F1,4=minf1,3,f1,2+f3,4,f2,4)+10其中f1,3=minf1,2,f2,3+7=10F2,4=minf2,3,f3,4+6=9當(dāng)n=6F1,6=minf1,5,f1,2+f3,6,f1,3+f4,6,f1,4+f5,6,f2,6+g(1,6)/g數(shù)組用來存放其中：f3,6=minf3,5,f3,4+f4,5,f4,6+g(3,6)對于一般情況有：F1,n=minf1,n-1

11、,f1,2+f3,n,-2J+fn-1,n,f2,n+g(1,n)fi,j=minfi,j-1,電j+1+fi+2,j,電i+2+fi+3,n,(m,nfi+1,j+g變形：P1015能量項鏈將鏈轉(zhuǎn)換成列：將1234復(fù)制一下，如4個數(shù)是：4325,復(fù)制一下，變成43254325下面只要求出maxF1,4,F2,5F4,79、最大乘積P1192題意：在N個數(shù)字中插入K個乘號，求最大乘積。樣例輸入：421231輸出：62算法：采用背包算法，窮舉乘號的位置。實際上這道題的命題者想到的算法是DP,請你寫出DP方程。用Fn,k表示在N個數(shù)中插入K個乘號的最大值先計算Fi,1i從2取到n,下面請寫出Fn,

12、k=?Fn,k=maxFn-1,k-1*A(n,n),Fn-2,k-1*A(n-1,n).Fk,k1*A(k+1,n)其中A(I,j)表示N串中從第i個字符取到第j個字符的整數(shù)。vari1,n,i,j,k:longint;max,s:qword;st:string;g:array1.20ofinteger;a:array1.20,1.20ofqword;f:array0.10,0.10ofqword;beginreadln(n,k);readln(st);fori:=1tondo/分解出i到j(luò)的數(shù)forj:=1tondoval(copy(st,i,j-i+1),ai,j);fori:=2ton

13、do求1個乘號的最大值beginmax:=0;forj:=1toi-1doifa1,j*aj+1,i>maxthenmax:=a1,j*aj+1,i;fi,1:=max;end;fori:=2tokdo/DP求K個乘號forj:=i+1ton-k+idobeginmax:=0;fori1:=j-1downtoidoiffi1,i-1*ai1+1,j>maxthenmax:=fi1,i-1*ai1+1,j;fj,i:=maxend;writeln(fn,k)end.10、花店櫥窗布置P1420輸入：35723524416521-41023-215-4-2020輸出：53說明：取的是2

14、45也就是：從5個里面怎樣選3個，得到最大值。每行選一個，下一個數(shù)在上一個數(shù)的后面列。用Fi,j表示在前i列中j行中選，每行選1個數(shù)，且列不斷增加，共j個數(shù)，得到的最大值。上例中最后要求的是F5,3=maxF4,2+a3,5F3,2+maxA3,4A3,5F2,2+maxA3,3A3,5以上是兩次DP。從而得到DP方程:Fi-1,j-1+aj,iFI,j=maxFi-2,j-1+maxaj,i-1-aj,iFj-1,j-1+maxaj,j-aj,ivari2,i1,n,i,j,k,max,max1:longint;a:array1.100,1.100oflongint;f:array0.100

15、,0.100oflongint;beginreadln(k,n);fori:=1tokdobeginforj:=1tondoread(ai,j);readln;end;f1,1:=a1,1;fori:=2tondoforj:=1toidobeginmax:=-maxlongint;fori1:=j-1toi-1dobeginmax1:=-maxlongint;fori2:=i1+1toidoifaj,i2>max1thenmax1:=aj,i2;ifmax1+fi1,j-1>maxthenmax:=max1+fi1,j-1;end;fi,j:=max;end;writeln(fn,

16、k)end.11、構(gòu)建雙塔P1466從N個數(shù)選部分?jǐn)?shù)，分成兩組，要求兩組的和相同，求最大的和，無法輸出：“Impossible1WNW100樣例：輸入：513452輸出：7樣例：13452和為15,當(dāng)然如果要分兩組，如果高度差為1,此時分組為：7、8;則F5,1=8,如果兩組的差為0,即F5,0則是所要求的最終解。Fi,j=X表示前i個數(shù)，高度差是j,這時的最大值是X因此，F(xiàn)5,1=8,表示取前5個數(shù)分兩組時，當(dāng)兩組差是1的時候，這時得到的最大值是8 ?，F(xiàn)在往前DP,根據(jù)4個數(shù)來求第5個數(shù)。(1)、第i件物品不選，F(xiàn)i-1,j(2)、第i件物品選，放到了較矮的那個塔上，而且矮塔仍然為矮塔，填補(bǔ)

17、了高度差一一一一*1一一-hJ(3)、第i件物品選，放到了較矮的那個塔上，但矮塔變成了高塔但有條件限制：hi>j(4)、第i件物品選，放到了較高的那個塔上，增加了高度差因此，可以用Fi-1,j-hi+hi條件限制：J>=hi設(shè)fi,j表示前i塊水晶，兩塔高度差為j時較高的那個塔的高度。DP方程：fi,j=maxfi-1,j,fi-1,j+hi,fi-1,hi-j+j(j<hi)fi,j=maxfi-1,j,fi-1,j+hi,fi-1,j-hi+hi(j>=hi)解析：fi-1,j表示不放第i塊水晶；fi-1,j+hi表示第i塊水晶放到了較矮的那個塔上，而且矮塔仍然為矮

18、塔，填補(bǔ)了高度差;fi-1,hi-j+j表示第i塊水晶放到了較矮的那個塔上，但是矮塔變成了高塔；fi-1,j-hi+hi表示第i塊水晶放到了較高的塔上，增加了高度差；邊界條件：如果剛開始的f值都為0的話，調(diào)試的時候會發(fā)現(xiàn)，有許多不合邏輯的答案，例如:h1=1,f1,2也會算出值為1,但其實是無法用高度為1的水晶搭出高度差大于等于2的雙塔的。所以要把所先把所有的f賦成-maxlongint,然后f0,0:=0。varf:array0.100,0.2000ofinteger;n,sum,i,j,k:integer;h:array1.100ofinteger;functionmax(x,y,z:in

19、teger):integer;beginmax:=x;ifmax<ythenmax:=y;ifmax<zthenmax:=z;end;beginreadln(n);sum:=0;fori:=1tondobeginread(hi);sum:=sum+hi;end;fori:=0tondoforj:=0tosumdofi,j:=-1000;f0,0:=0;fori:=1tondoforj:=0tosumdobeginifhi<jthenfi,j:=max(fi-1,j,fi-1,j+hi,fi-1,j-hi+hi)elsefi,j:=max(fi-1,j,fi-1,j+hi,fi

20、-1,hi-j+j);end;iffn,0>0thenwrite(fn,0)elsewrite('Impossible');end.12、垃圾處理、任務(wù)分配有兩行數(shù)，每行N個，每列選1個，共選N個數(shù)，將每行所選的數(shù)相加，結(jié)果取兩個和的最大值，求這個最大值的最小值。樣例輸入：5/每行N個數(shù)，以下兩行24145/ai21341/bi輸出：5第一行取3、4歹U,第二行取1、2、5列設(shè)Fi,j表示：完成前i項任務(wù)，若第1個人花了j分鐘，那么第二個人最少花Fi,j分鐘。F2,0=3F2,1=3F2,2=1F2,3=1F2,4=1F2,6=0F2,20=0下面求F3,0=6F3,1可

21、以用兩種方法的最小值來表示：（1） 第3件任務(wù)第一個人不做，則為F2,1+B3（2） 第3件任務(wù)第一個人做，前提是時間夠用，即j>=ai,則為F2,0那么有以下DP方程：Fi,j=MinFi-1,j+Bi,Fi-1,j-Ai邊界F0,0=0,13、NOP2000方格取數(shù)（一）問題描述設(shè)有N*N的方格圖（NW8）,我們將其中的某些方格中填入正整數(shù)，而其他的方格中則放入數(shù)字0。如下圖所示（見樣例）：4向右A12345678100000000200130060030000700040001400005021000400向6001500000下7014000000800000000B某人從圖的左

22、上角的A點出發(fā)，可以向下行走，也可以向右走，直到到達(dá)右下角的點。在走過的路上，他可以取走方格中的數(shù)(取走后的方格中將變?yōu)閿?shù)字0)。此人從A點到B點共走兩次，試找出2條這樣的路徑，使得取得的數(shù)之和為最大。輸A-輸入的第一行為一個整數(shù)N(表示N*N的方格圖)，接下來的每行有三個整數(shù)，前兩個表示位置，第三個數(shù)為該位置上所放的數(shù)。一行單獨的0表示輸入結(jié)束。只需輸出一個整數(shù)，表示2條路徑上取得的最大的和。樣例輸入823132 663 574 4145 2216 647 3158 214000輸出67(二)問題分析本題是從1997年國際信息學(xué)奧林匹克的障礙物探測器一題簡化而來，如果人只能從A點到B點走一次

23、，就是以前的樹塔問題，可以用動態(tài)規(guī)劃算法求出從A點到B點的最優(yōu)路徑。具體的算法描述如下：從A點開始，向右和向下遞推，依次求出從A點出發(fā)到達(dá)當(dāng)前位置(i,j)所能取得的最大的數(shù)之和，存放在sum數(shù)組中，原始數(shù)據(jù)經(jīng)過車t換后用二維數(shù)組data存儲，為方便處理，對數(shù)組sum和data加進(jìn)零行與零列，并置它們的零行與零列元素為0。易知sumi,j=atai<，j當(dāng)i=0或尸0max工(sumi-1,j,sumi,j-1)+datai,j當(dāng)i>0,且j>0summ,n就是最大值，如果要求出具體的走法，可以通過倒推求得，具體算法如下：置sum數(shù)組零行與零列元素為0fori:=1tondo

24、forj:=1tondoifsumi-1,j>sumi,j-1thensumi,j:=sumi-1,j+datai,jelsesumi,j:=sumi,j-1+datai,j;/產(chǎn)生sum數(shù)組的值i:=n;j:=n;while(i>1)or(j>1)do/以下是求具體的取法if(i>1)and(sumi,j=sumi-1,j+datai,j)thenbegindatai,j:=-1;i:=i-1endelsebegindatai,j:=-1;j:=j-1end;data1,1:=-1;凡是被標(biāo)上-1的格子即構(gòu)成了從A點到B點的一條最優(yōu)路徑。那么是否可以按最優(yōu)路徑連續(xù)走兩

25、次而取得最大數(shù)和呢？這是一種很自然的想法，并且對樣例而言也是正確的，雖然這一算法保證了連續(xù)的兩次走法都是最優(yōu)的，但卻不能保證總體最優(yōu)，相應(yīng)的反例也不難給出，請看下圖：3233443323344I33233443圖一圖二圖三圖二按最優(yōu)路徑走一次后，余下的兩個數(shù)2和3就不可能同時取倒了，而按圖三中的非最優(yōu)路徑走一次后卻能取得全部的數(shù)，這是因為兩次走法之間的協(xié)作是十分重要的，而圖2中的走法并不能考慮全局，因此這一算法只能算是“貪心算法”。雖然在一些情況下，貪心算法也能夠產(chǎn)生最優(yōu)解，但總的來說“貪心算法”是一種有明顯缺陷的算法。實際上本問題完全可以用動態(tài)規(guī)劃解決，只是遞推起來更為復(fù)雜些而已，前面在考慮

26、只走一次的情況，只需考慮一個人到達(dá)某個格子（i,j）的情況，得出sumi,j=max（sumi-1,j,sumi,j-1）+datai,j,現(xiàn)在考慮兩個人同時從A出發(fā)，則需考慮兩個人到達(dá)任意兩個格子（i1,j1）與（i2,j2）的情況，顯然要到達(dá)這兩個格子，其前一狀態(tài)必為下列四種情況之一：（2,4）、（2,3）、（1,4）、（1,3）坐標(biāo)如下：(1)、(i1-1,j1),(i2-1,j2);(2)、(i1-1,j1),(i2,j2-1);(3)、(i1,j1-1),(i2-1,j2);(4)、(i1,j1-1),(i2,j2-1);用一個四維數(shù)組sumi1,j1,i2,j2來表示到達(dá)i1,j1

27、與i2,j2時的最大值，設(shè)P=max(sumi1-1,j1,i2-1,j2,sumi1-1,j1,i2,j2-1,sumi1,j1-1,i2-1,j2,sumi1,j1-1,i2,j2-1),則0廠當(dāng)i1=0或j1=0或i2=0或j2=0sumi1,j1,i2P2+=datafjl,j1當(dāng)i1,j1,i2,j2均不為零，且i1=i2,j1=j2p+datai1j1+datai2,j2當(dāng)i1,j1,i2,j2均不為零，且i1豐i2或j1wj2（三）程序清單constmaxn=10;typearraytype=array0.maxn,0.maxnoflongint;vari,j,k,n,i1,i2

28、,j1,j2:longint;data:arraytype;sum:array0.maxn,0.maxn,0.maxn,0.maxnoflongint;functionmax(x,y:longint):longint;beginifx>ythenmax:=xelsemax:=y;end;BEGINfori:=1tomaxndoforj:=1tomaxndodatai,j:=0;readln(n);repeatreadln(i,j,k);datai,j:=kuntil(i=0)and(j=0)and(k=0);fillchar(sum,sizeof(sum),0);fori1:=1tond

29、oforj1:=1tondofori2:=1tondoforj2:=1tondobeginsumi1,j1,i2,j2:=max(sumi1-1,j1,i2-1,j2,sumi1,j1,i2,j2);sumi1,j1,i2,j2:=max(sumi1-1,j1,i2,j2-1,sumi1,j1,i2,j2);sumi1,j1,i2,j2:=max(sumi1,j1-1,i2-1,j2,sumi1,j1,i2,j2);sumi1,j1,i2,j2:=max(sumi1,j1-1,i2,j2-1,sumi1,j1,i2,j2);sumi1,j1,i2,j2:=sumi1,j1,i2,j2+data

30、i1,j1;加上i1,j1if(i1<>i2)or(j1<>j2)/兩點不同的時候再加上i2,j2thensumi1,j1,i2,j2:=sumi1,j1,i2,j2+datai2,j2end;writeln(sumn,n,n,n)END.NOIP2008傳紙條【問題描述】小淵和小軒是好朋友也是同班同學(xué)，他們在一起總有談不完的話題。一次素質(zhì)拓展活動中，班上同學(xué)安排做成一個m行n列的矩陣，而小淵和小軒被安排在矩陣對角線的兩端，因此，他們就無法直接交談了。幸運(yùn)的是，他們可以通過傳紙條來進(jìn)行交流。紙條要經(jīng)由許多同學(xué)傳到對方手里，小淵坐在矩陣的左上角，坐標(biāo)(1,1),小軒坐在矩

31、陣的右下角，坐標(biāo)(m,n)。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。在活動進(jìn)行中，小淵希望給小軒傳遞一張紙條，同時希望小軒給他回復(fù)。班里每個同學(xué)都可以幫他們傳遞，但只會幫他們一次，也就是說如果此人在小淵遞給小軒紙條的時候幫忙，那么在小軒遞給小淵的時候就不會再幫忙。反之亦然。還有一件事情需要注意，全班每個同學(xué)愿意幫忙的好感度有高有低(注意：小淵和小軒的好心程度沒有定義，輸入時用0表示)，可以用一個0-100的自然數(shù)來表示，數(shù)越大表示越好心。小淵和小軒希望盡可能找好心程度高的同學(xué)來幫忙傳紙條，即找到來回兩條傳遞路徑，使得這兩條路徑上同學(xué)的好心程度只和

32、最大。現(xiàn)在，請你幫助小淵和小軒找到這樣的兩條路徑?！据斎搿枯斎胛募essage.in的第一行有2個用空格隔開的整數(shù)m和n,表示班里有m行n列(1<=m,n<=50)。接下來的m行是一個m*n的矩陣，矩陣中第i行j列的整數(shù)表示坐在第i行j列的學(xué)生的好心程度。每行的n個整數(shù)之間用空格隔開?！据敵觥枯敵鑫募essage.out共一行，包含一個整數(shù)，表示來回兩條路上參與傳遞紙條的學(xué)生的好心程度之和的最大值?！据斎胼敵鰳永縨essage.inmessage.out3303928557034【限制】30%的數(shù)據(jù)滿足：1<=m,n<=10100%的數(shù)據(jù)滿足：1<=m,n&

33、lt;=50分析該題與上題比較，雖然是從兩個方向傳，實際上可以理解為從開始出發(fā)取兩個格子，一直到最后，不過在取的時候不允許兩點相交。如例子中的取法可以分解為：0-1-2III1-2-3III2-3-4設(shè)i1,j1的位置在i2,j2的左下方，則有：i1>i2,j1<j2,因此在取格子程序的循環(huán)中增加一個條件就可以了，而且不用考慮兩點相同的時候。另外，不同的是m行，n列，數(shù)據(jù)的規(guī)模到50。程序如下：constmaxn=5Qtypearraytype=array1.maxn,1.maxnoflongint;varm,i,j,k,n,i1,i2,j1,j2:longint;data:arr

34、aytype;sum:array0.maxn,0.maxn,0.maxn,0.maxnoflongint;functionmax(x,y:longint):longint;beginifx>ythenmax:=xelsemax:=y;end;BEGINassign(input,'message.in');reset(input);assign(output,'message.out');rewrite(output);readln(m,n);fori:=1tomdoforj:=1tondoread(datai,j);fillchar(sum,sizeof(

35、sum),0);fori1:=1tomdoforj1:=1tondofori2:=1tomdoforj2:=1tondoif(i1>i2)and(j1<j2)thenbeginsumi1,j1,i2,j2:=max(sumi1-1,j1,i2-1,j2,sumi1,j1,i2,j2);sumi1,j1,i2,j2:=max(sumi1-1,j1,i2,j2-1,sumi1,j1,i2,j2);sumi1,j1,i2,j2:=max(sumi1,j1-1,i2-1,j2,sumi1,j1,i2,j2);sumi1,j1,i2,j2:=max(sumi1,j1-1,i2,j2-1,su

36、mi1,j1,i2,j2);sumi1,j1,i2,j2:=sumi1,j1,i2,j2+datai1,j1+datai2,j2;end;writeln(summ,n-1,m-1,n);close(input);close(output);END.14、烏龜棋（NOIP2010I高組復(fù)賽第二題）小明過生日的時候，爸爸送給他一副烏龜棋當(dāng)作禮物。烏龜棋的棋盤是一行N個格子，每個格子上一個分?jǐn)?shù)（非負(fù)整數(shù)）。棋盤第1格是唯一的起點，第N格是終點，游戲要求玩家控制一個烏龜棋子從起點出發(fā)走到終點。12345N烏龜棋中M張爬行卡片，分成4種不同的類型（M張卡片中不一定包含所有4種類型的卡片，見樣例），每種類

37、型的卡片上分別標(biāo)有1、2、3、4四個數(shù)字之一，表示使用這種卡片后，烏龜棋子將向前爬行相應(yīng)的格子數(shù)。游戲中，玩家每次需要從所有的爬行卡片中選擇一張之前沒有使用過的爬行卡片，控制烏龜棋子前進(jìn)相應(yīng)的格子數(shù)，每張卡片只能使用一次。游戲中，烏龜棋子自動獲得起點格子的分?jǐn)?shù)，并且在后續(xù)的爬行中每到達(dá)一個格子，就得到該格子相應(yīng)的分?jǐn)?shù)。玩家最終游戲得分就是烏龜棋子從起點到終點過程中到過的所有格子的分?jǐn)?shù)總和。很明顯，用不同的爬行卡片使用順序會使得最終游戲的得分不同，小明想要找到一種卡片使用順序使得最終游戲得分最多?，F(xiàn)在，告訴你棋盤上每個格子的分?jǐn)?shù)和所有的爬行卡片，你能告訴小明，他最多能得到多少分嗎？輸入文件的每行中兩個數(shù)之間用一個空格隔開。第1行2個正整數(shù)N和M分別表示棋盤格子