动态规划解析

1、第一题导弹拦截本题第一问实际上是给出数列a1.an,求最长非递增序列的长度，容易想到以n来划分子问题，即分别求a1.an-1, a1.an-2, , a1,中最长非递增序列长度，但各级子问题之间不易建立转化关系将子问题具体一些，我们可以用fk表示数列a1.ak中以ak结尾的最长非递增序列的长度，题目所求即为maxf1.n。转移方程为fn=maxfk+1;(0<=k<n,an<=ak )设a0= -maxint,f0=0;第二问可以用贪心做，设拦截前k个导弹用o2个系统，其最后拦截的高度分别为l1.lo2,则拦截第k+1个导弹时，找能够拦截这枚导弹的系统中最后拦截高度最小的，若

2、没有这样的系统则新增一个系统。附源程序：const max = 10000;type arr = array0.maxof integer;var d,l : arr; i,j,k,m,n,o1,o2,t : longint;procedure input; begin fillchar(d,sizeof(d),0); fillchar(l,sizeof(l),0); writeln('input:'); i:=0; repeat i:=i+1; read(di); until eoln; t:=i; o1:=0; o2:=0; end;procedure output; be

3、gin writeln('Output:'); writeln(o1); writeln(o2); end;procedure main1; begin lt:=1; for i:=t-1 downto 1 do begin k:=0; for j:=i+1 to t do if (lj>k)and(di>=dj) then k:=lj; li:=k+1; end; for i:=1 to t do if li>o1 then o1:=li; end;procedure main2; begin for i:=0 to t do li:=maxint; o2:

4、=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<=k<j)的解有关，即问题的最

5、优解包含了子问题的最优解，具备最优子结构。转移方程为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;

6、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)

7、and (now<old) or (job=2) and (now>old) then try:=true else try:=false; end;procedure get(first,last,job:integer); var k:Word; now:longint; begin k:=first; while k<>last do begin now:=count(first,k,last); if try(now,rock_bestfirst,last,job) then begin rock_bestfirst,last:=now; rock_kfirst

8、,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;

9、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=las

10、t) 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

11、 mod n)+1:=false; if last>=first then s:=totlast-totfirst-1 else s:=totlast+totn-totfirst-1; i:=first; while i<>last 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:=

12、(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-1<rock_bestfirst,last) and (job=1) or (rock_besti,i-1>rock_bestfirst,last) and (job=2) then begin first:=i; last:=i-1; end; out(first,last); writeln(totn); e

13、nd;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

14、= 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; numb

15、er:=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 : longi

16、nt; 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 j>i-1 then continue; max:=0; for p:=i-1 downto 1 do begin lin:=mp,j-1*number(p+1,i); if lin>max then max:=lin; end; mi,j:=max; end; end; end;begin input; main; output;end.第四题方格取数先看游戏者从A到B只走一次的情况。只能向

17、下或向右走，这隐含了格子之间的拟序关系，可以根据这种关系划分子问题。走到格（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,

18、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(

19、x,y:longint):longint;begin if x>y 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 d

20、o begin if sumi1-1,j1,i2-1,j2>sumi1,j1,i2,j2 then sumi1,j1,i2,j2:=sumi1-1,j1,i2-1,j2; if sumi1-1,j1,i2,j2-1>sumi1,j1,i2,j2 then sumi1,j1,i2,j2:=sumi1-1,j1,i2,j2-1; if sumi1,j1-1,i2-1,j2>sumi1,j1,i2,j2 then sumi1,j1,i2,j2:=sumi1,j1-1,i2-1,j2; if sumi1,j1-1,i2,j2-1>sumi1,j1,i2,j2 then sumi

21、1,j1,i2,j2:=sumi1,j1-1,i2,j2-1; sumi1,j1,i2,j2:=sumi1,j1,i2,j2+datai1,j1; if (i1<>i2) or (j1<>j2) 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

22、为这种情况下的一种划分，且ai<=ai+1(1<=i<j),则a11.aj1对应于将数i-j分为j份的一种划分，且这种对应是一一对应，所以这种情况包含的方法总数为fi-j,j。附源程序：program dp; const outputfile='output.txt' var i,j,k,m,n:integer; f:array0.200,0.7of longint; begin read(n,m); f0,0:=1; for i:=1 to n do for j:=1 to m do if i>=j then fi,j:=fi-j,j+fi-1,j-1

23、; 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开

24、头的单词的最小长度，若没有这样的单词，则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-1<=ll)。由于当前阶段的状态只于上一阶段有关，实现时运用了滚动数组。附源程序：$A+,B-,D-,E+,F-,G+,I-,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+$M 16384,0,655360const maxn =200; maxl =20; max word's lengtht

25、ype ftype =array0.1,0.maxnof integer;var map :array1.maxn,1.maxnof byte; ff :text; nn,k,l,i,maxll :integer; procedure Init; var i,j,p,o,ll :integer; s,t,word :string; ch :char; begin readln(ff,p,k); s:='' for i:=1 to p do begin for j:=1 to 20 do begin read(ff,ch); s:=s+ch; end; readln(ff); e

26、nd; l:=length(s); readln(ff,p); fillchar(map,sizeof(map),0); maxll:=0; for i:=1 to p do begin readln(ff,word); while wordlength(word)=' ' do delete(word,length(word),1); t:=s; j:=pos(word,t); o:=0; ll:=length(word); if ll>maxll then maxll:=ll; while j>0 do begin mapo+j,ll:=1; delete(t,

27、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-i

28、1; fillchar(gi2,sizeof(gi2),0); for s:=i-1 to l-k+i-1 do begin if l-k+i-s>maxll 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-1>fp1,ll then fp2,ll:=fp2,ll-1 else fp2,ll:=fp1,l

29、l; if (mapp,ll-p+1>0)and(fp2,ll<fp1,ll+1) then fp2,ll:=fp1,ll+1; if gi2,ll<fp2,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.第七题低价买入，更低价买入本题实际

30、上是给出数列a1.an,求最长非递增序列的长度，我们可以用fk表示数列a1.ak中以ak结尾的最长非递增序列的长度，题目所求即为maxf1.n。转移方程为fn=maxfk+1;(0<=k<n,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:WINDOWSDESKTOPTESTSTOCKSTOC

31、K.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 (PRICEJ<PRICEI) AND (LISTJ>LISTI-1) THEN LISTI:=LISTJ+1; FOR I:=1 TO N DO IF LISTI&g

32、t;MAX 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,

33、初始时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,

34、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 i<j do begin while (i<j)and(piej.time>=x.time) do dec(j); piei:=piej; while (i<j)and(piei.time<=x.time) do inc(i); piej:=piei; end; piei:=x; Sort(l,i-1);

35、 Sort(i+1,r); end; begin assign(input,'pie.in'); reset(input); readln(w,h); n:=0; while not eof(input) do begin n:=n+1; readln(s,pien.pos,v,pien.mark); pien.time:=s+(h-1)div v; if (h-1)mod v>0 then inc(pien.time); end; close(input); Sort(1,n); end; procedure Main; var f :array-1.maxnof ft

36、ype; 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(max<fik+c) then begin max:=fik+c; j:=c; end; print(i,k+j); writeln(-j); end; begin for i:=-1 to maxn do begin new(fi); fillchar(fi,si

37、zeof(fi),0); end; k:=1; f0w div 2+1:=1; for i:=0 to pien.time do begin if i>0 then for j:=1 to w do begin max:=0; for c:=-2 to 2 do if (j+c>=1)and(j+c<=w)then begin if (fi-1j+c>max) then max:=fi-1j+c; end; fij:=max; end; while (k<=n)and(i=piek.time) do begin if fipiek.pos>0 then fi

38、piek.pos:=fipiek.pos+piek.mark; k:=k+1; end; end; max:=1; for j:=1 to w do if fij>max 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首歌。对

39、于第一种情况，要求用j张唱片外加k-timei分钟（k>=timei时）或用j-1张唱片外加t-timei分钟（k<timei时）在前i-1首歌中录制的歌曲数最大；对于第二种情况，要求用j张唱片外加k分钟在前i-1首歌中录制的歌曲数最大。该问题具备最优子结构。动态规划转移方程为fi,j,k=maxfi,j,k-timei+1,fi-1,j,k(k>=timei)fi,j,k=maxfi,j-1,t-timei+1,fi-1,j,k(k<timei)fi,j,0=fi,j-1,t;附源程序：const maxn =20;var n,m,t :integer; time :

40、array1.maxnof shortint; procedure Init; var ff :text; i,j :integer; begin assign(ff,'record.in'); reset(ff); readln(ff,n,t,m); for i:=1 to n do read(ff,timei); close(ff); end; procedure Main; var f :array0.maxn,0.maxn,0.maxnof shortint; i,j,k,ii,max,a,b,c :integer; begin fillchar(f,sizeof(f),0); a:=0; for i:=1 to n do begin if i>m then a:=m else a:=i; for