《动态规划解析》word版.doc

第一题导弹拦截本题第一问实际上是给出数列a1.an,求最长非递增序列的长度，容易想到以n来划分子问题，即分别求a1.an-1, a1.an-2, , a1,中最长非递增序列长度，但各级子问题之间不易建立转化关系将子问题具体一些，我们可以用fk表示数列a1.ak中以ak结尾的最长非递增序列的长度，题目所求即为maxf1.n。转移方程为fn=maxfk+1;(0=kn,ank)and(di=dj) then k:=lj; li:=k+1; end; for i:=1 to t do if lio1 then o1:=li; end;procedure main2; begin for i:=0 to t do li:=maxint; o2:=1; for i:=1 to t do begin k:=0; for j:=1 to o2 do if (lj=di)and(lj=lk) then k:=j; if k=0 then begin o2:=o2+1; k:=o2; end; lk:=di; end; end;begin input; main1; main2; output;end.第二题石子合并设fi,j(i=j)表示将第i堆到第j堆石子合并为一堆所得的最大分数（最小时类似）。问题所求即为f1,n。根据合并规则，fi,j的解只于fi,k,fk+1,j(i=kj)的解有关，即问题的最优解包含了子问题的最优解，具备最优子结构。转移方程为fi,j=fi,k+fk+1,j+dp;初始时fk,k=0(1=k=n);附源程序：Program gether_stone; type Trock_best = Array1.100,1.100 of longint; Trock_k = Array1.100,1.100 of byte; Tstone = Array0.100 of word; Tbak = Array1.100 of boolean; var rock_best:Trock_best; rock_k:Trock_k; stone,tot:Tstone; stone1:Tstone; bak:Tbak; n:Word;function count(first,k,last:Word):longint; var s1:longint; begin if first=last then s1:=totlast-totfirst-1 else s1:=totn+totlast-totfirst-1; count:=rock_bestfirst,k+rock_best(k mod n)+1,last+s1; end;function try(now,old:longint;job:byte):boolean; begin if (job=1) and (nowold) then try:=true else try:=false; end;procedure get(first,last,job:integer); var k:Word; now:longint; begin k:=first; while klast do begin now:=count(first,k,last); if try(now,rock_bestfirst,last,job) then begin rock_bestfirst,last:=now; rock_kfirst,last:=k; end; k:=(k mod n)+1; end; end;procedure init; var i:Word; begin assign(input,input.txt); reset(input); readln(n); for i:=1 to n do read(stonei); close(input); tot0:=0; for i:=1 to n do toti:=toti-1+stonei; new(rock_best); assign(output,output.txt); rewrite(output); end;procedure into(job:byte); var i:Word; begin if job=1 then fillchar(rock_best,sizeof(rock_best),$1) else fillchar(rock_best,sizeof(rock_best),0); fillchar(rock_k,sizeof(rock_k),0); for i:=1 to n do rock_besti,i:=stonei; end;procedure out(first,last:byte); var i,s:Word; begin if not(first mod n)+1=last) or (first=last) then begin out(first,rock_kfirst,last); out(rock_kfirst,last mod n)+1,last); end; if first=last then exit; for i:=1 to n do if baki=true then begin if (i=first) or (i=(rock_kfirst,lastmod n)+1) then write(-); write(stone1i, ); end; writeln; bak(rock_kfirst,last mod n)+1:=false; if last=first then s:=totlast-totfirst-1 else s:=totlast+totn-totfirst-1; i:=first; while ilast do begin stone1i:=s; i:=(i mod n)+1; end; stone1last:=s; end;procedure work(job:byte); var i,j,k,first,last:Word; begin into(job); for i:=1 to n do for j:=2 to n do begin k:=(i+j-2) mod n)+1; get(i,j,job); end; stone1:=stone; fillchar(bak,sizeof(bak),true); first:=1; last:=n; for i:=2 to n do if (rock_besti,i-1rock_bestfirst,last) and (job=2) then begin first:=i; last:=i-1; end; out(first,last); writeln(totn); end;begin init; work(1); work(2); close(output);end.第三题乘积最大问题给出了一个数字串s，求向其中加k个乘号后的最大乘积。设fi,j表示向串s1.i中加j个乘号后的最大乘积，n=length(s)。问题所求即为fn,k。假设最优解中第k个乘号放在第i个字符后，则前k-1个乘号的放置必为子问题“向串s1.i中加k-1个乘号”的最优解，所以该问题具备最优子结构。设numi,j表示串si.j所表示的数字，动态规划的转移方程为fi,j=fp,j-1*nump+1,i,初始时有fi,0=num1,i。附源程序：const max1 = 30; max2 = 20;type arr1 = array1.max1,0.max2of longint; arr2 = array1.max1of longint;var m : arr1; num : arr2; f : text; i,j,k,p,q,l,n : longint; st : string; code : integer;function number(a,b:integer):longint; var i,j,m : longint; begin m:=0; j:=1; for i:=b downto a do begin m:=m+numi*j; j:=j*10; end; number:=m; end;procedure input; begin fillchar(m,sizeof(m),0); fillchar(num,sizeof(num),0); writeln(Input:); readln(n,k); readln(st); for i:=1 to n do numi:=ord(sti)-ord(0); end;procedure output; begin writeln(Output:); writeln(mn,k); end;procedure main; var lin,max : longint; begin for i:=1 to n do mi,0:=number(1,i); for i:=2 to n do begin for j:=1 to 20 do begin if ji-1 then continue; max:=0; for p:=i-1 downto 1 do begin lin:=mp,j-1*number(p+1,i); if linmax then max:=lin; end; mi,j:=max; end; end; end;begin input; main; output;end.第四题方格取数先看游戏者从A到B只走一次的情况。只能向下或向右走，这隐含了格子之间的拟序关系，可以根据这种关系划分子问题。走到格（x,y）所得到的最大分值只于前一步在格（x-1,y）或（x,y-1）所得到的最大分值有关，即问题具备最优子结构。设fx,y表示走到格（x,y）所得到的最大分值，datax,y表示格（x,y）的分值，动态规划的转移方程为fx,y=maxfx-1,y,fx,y-1+datax,y;初始时f1,1=data1,1。类似的，对于走两次的情况，设fi1,j1,i2,j2表示第一，二条路线分别到格（i1,j1），（i2,j2）时得到的最大分值。动态规划转移方程为fi1,j1,i2,j2=maxfi1-1,j1,i2,j2,fi1,j1-1,i2,j2,fi1,j1,i2-1,j2, fi1,j1,i2,j2-1+datai1,j1+datai2,j2(当(i1,j1)=(i2,j2)时只加一次)，初始时f1,1,1,1=data1,1。附源程序：program get_number;const maxn=10;type arraytype=array 0.maxn,0.maxn of longint;var i,j,k,n,i1,i2,j1,j2:longint; data:arraytype; sum:array 0.maxn,0.maxn,0.maxn,0.maxn of longint;function max(x,y:longint):longint;begin if xy then max:=x else max:=y;end;begin for i:=1 to maxn do for j:=1 to maxn do datai,j:=0; readln(n); repeat readln(i,j,k); datai,j:=k; until (i=0) and (j=0) and (k=0); fillchar(sum,sizeof(sum),0); for i1:=1 to n do for j1:=1 to n do for i2:=1 to n do for j2:=1 to n do begin if sumi1-1,j1,i2-1,j2sumi1,j1,i2,j2 then sumi1,j1,i2,j2:=sumi1-1,j1,i2-1,j2; if sumi1-1,j1,i2,j2-1sumi1,j1,i2,j2 then sumi1,j1,i2,j2:=sumi1-1,j1,i2,j2-1; if sumi1,j1-1,i2-1,j2sumi1,j1,i2,j2 then sumi1,j1,i2,j2:=sumi1,j1-1,i2-1,j2; if sumi1,j1-1,i2,j2-1sumi1,j1,i2,j2 then sumi1,j1,i2,j2:=sumi1,j1-1,i2,j2-1; sumi1,j1,i2,j2:=sumi1,j1,i2,j2+datai1,j1; if (i1i2) or (j1j2) then sumi1,j1,i2,j2:=sumi1,j1,i2,j2+datai2,j2; end; writeln(Maxscore=,sumn,n,n,n);end.第五题数的划分设fi,j（i=j）表示将数i分成j份的方法总数，分两种情况，一是划分后最小的数为1，这种情况包含的方法总数为fi-1,j-1,一是划分后最小的数大于1，设a1.aj为这种情况下的一种划分，且ai=ai+1(1=i=j then fi,j:=fi-j,j+fi-1,j-1; assign(output,outputfile); rewrite(output); writeln(fn,m); close(output); end.第六题统计单词个数设gi,l表示将字串st1.l分成i份所能得到的最大单词个数，fp,ll表示字串stp.ll中包含的最大单词个数。将字串st1.l分成i份的最优解（设其中第i份为sts .l）中一定包含了子问题将字串st1.s分成i-1份的最优解，问题具备最优子结构。转移方程为gi,ll= gi-1,s+fs+1,ll 。如何求fp,ll呢？若有两个单词在串st中占有同一个首字母，显然应该选长度小的一个。可以设wpi表示st中以si开头的单词的最小长度，若没有这样的单词，则wpi:=maxint;串stp.ll中包含的单词个数即为 op(wpi+i-1=ll),函数op(命题I)当I为真时值为1，I为假时值为0。若先求fp+1,ll后求fp,ll,可以有fp,ll=fp+1,ll+op(wpp+p-1maxll then maxll:=ll; while j0 do begin mapo+j,ll:=1; delete(t,1,j); o:=o+j; j:=pos(word,t); end; end; for i:=1 to l do for j:=2 to l-i+1 do if (mapi,j=0)and(mapi,j-1=1) then mapi,j:=1; end; procedure Main; var i,j,i1,i2,s,ll,o,p,p1,p2,lw :integer; g :array0.1,0.maxnof integer; f :ftype; begin fillchar(g,sizeof(g),0); for i:=1 to k do begin i1:=i mod 2; i2:=1-i1; fillchar(gi2,sizeof(gi2),0); for s:=i-1 to l-k+i-1 do begin if l-k+i-smaxll then o:=maxll else o:=l-k+i; fillchar(f,sizeof(f),0); for p:=s+1 to o do begin p1:=p mod 2; p2:=1-p1; fillchar(fp2,sizeof(fp2),0); for ll:=p to o do begin if fp2,ll-1fp1,ll then fp2,ll:=fp2,ll-1 else fp2,ll:=fp1,ll; if (mapp,ll-p+10)and(fp2,llfp1,ll+1) then fp2,ll:=fp1,ll+1; if gi2,llfp2,ll+gi1,s then gi2,ll:=fp2,ll+gi1,s end; end; end; end; writeln(gi2,l); end;begin assign(ff,input3.dat); reset(ff); readln(ff,nn); for i:=1 to nn do begin Init; Main; end; close(ff);end.第七题低价买入，更低价买入本题实际上是给出数列a1.an,求最长非递增序列的长度，我们可以用fk表示数列a1.ak中以ak结尾的最长非递增序列的长度，题目所求即为maxf1.n。转移方程为fn=maxfk+1;(0=kn,an=ak )初始时，f0=0,a0= -maxint.VAR N:WORD; PRICE:ARRAY1.5000 OF REAL; LIST:ARRAY1.5000 OF WORD; MAX,TOTAL:WORD; PROCEDURE INIT; VAR F:TEXT; I:WORD; BEGIN ASSIGN(F,C:WINDOWSDESKTOPTESTSTOCKSTOCK.IN7); RESET(F); READLN(F,N); FOR I:=1 TO N DO READLN(F,PRICEI); CLOSE(F); MAX:=0; TOTAL:=0; END; PROCEDURE CALC; VAR I,J:WORD; BEGIN FOR I:=1 TO N DO LISTI:=1; FOR I:=N DOWNTO 1 DO FOR J:=i+1 TO N DO IF (PRICEJLISTI-1) THEN LISTI:=LISTJ+1; FOR I:=1 TO N DO IF LISTIMAX THEN MAX:=LISTI; WRITELN(MAX); END; BEGIN INIT; CALC; END.第九题免费馅饼设fi,j表示从时刻i(不包含这点，且游戏者在这秒内位于位置j)到游戏结束这段时间内游戏者所能得到的最大分值。显然f0,w div 2+1为问题解。若游戏者在时刻i位于位置j则他在i+1时刻只能从位置j-2.j+2中选择一个，并且使得以后的得分最大，即该问题具备最优子结构。设geti,j表示游戏者在时刻i（不包含）到时刻i+1(包含)这段时间内位于位置j所接到的馅饼分值总和。转移方程为fi,j= fi+1,p+geti,j; 设游戏结束的时刻为maxe,初始时fmaxe,1.w=0。对于决策，可以用数组记录，也可以直接利用已求得的状态数组f进行比较。$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+$M 65520,0,655360const maxn =1000; maxm =100;type pietype =record time :integer; mark,pos :shortint; end; ftype =array1.maxmof word;var n,w :integer; pie :array1.maxnof pietype; procedure Init; var i,h,s,t,v :integer; procedure Sort(l,r:integer); var i,j :integer; x :pietype; begin if l=r then exit; i:=l; j:=r; x:=piei; while ij do begin while (i=x.time) do dec(j); piei:=piej; while (ij)and(piei.time0 then inc(pien.time); end; close(input); Sort(1,n); end; procedure Main; var f :array-1.maxnof ftype; i,j,k,c,max :integer; procedure Print(i,k:integer); var j,c:integer; begin if i=0 then exit; max:=0; i:=i-1; for c:=-2 to 2 do if (k+c=1)and(k+c=w)and(max0 then for j:=1 to w do begin max:=0; for c:=-2 to 2 do if (j+c=1)and(j+cmax) then max:=fi-1j+c; end; fij:=max; end; while (k0 then fipiek.pos:=fipiek.pos+piek.mark; k:=k+1; end; end; max:=1; for j:=1 to w do if fijmax then begin max:=fij; k:=j; end; writeln(max-1); Print(i,k); end;begin Init; Main;end.第十题Raucous Rockers 演唱组设timei为第i首歌的长度，fi,j,k表示用j张唱片外加k分钟能在前i首歌中录制的最大歌曲数，问题所求即为fn,m,0。用j张唱片外加k分钟在前i首歌中有选择地录制可分两种情况，即录制或不录制第i首歌。对于第一种情况，要求用j张唱片外加k-timei分钟（k=timei时）或用j-1张唱片外加t-timei分钟（k=timei)fi,j,k=maxfi,j-1,t-timei+1,fi-1,j,k(km then a:=m else a:=i; for j:=0 to a do begin for k:=0 to t-1 do if (j0)or(k=timei) then begin ii:=i-1; if kfii,j,k then fi,j,k:=fii,b,c+1 else fi,j,k:=fii,j,k; end; if (j0)and(fi,j,tfi,j+1,0) then fi,j+1,0:=f