《动态规划题目及其代码》由会员分享，可在线阅读，更多相关《动态规划题目及其代码（12页珍藏版）》请在金锄头文库上搜索。
1、动态规划题目及其代码 By LYLtim1、数塔问题(tower.pas)设有一个三角形的数塔，如下图所示。顶点结点称为根结点，每个结点有一个整数数值。从顶点出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。【样例输入】tower.in5 数塔层数1311 812 7 266 14 15 812 7 13 24 11【样例输出】tower.outmax=86【参考程序】uses math;var n,i,j:byte; a:array1.10,1.10of word; f:array1.10,1.10of word;begin assign(input
2、,tower.in);reset(input); assign(output,tower.out);rewrite(output); readln(n); for i:=1 to n do begin for j:=1 to i do read(ai,j); readln; end; fillchar(f,sizeof(f),0); for i:=1 to n do fn,i:=an,i; for i:=n-1 downto 1 do for j:=1 to i do fi,j:=max(fi+1,j,fi+1,j+1)+ai,j; writeln(max=,f1,1); close(inpu
3、t);close(output);end.2、拦截导弹(missile.pas) 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。【样例输入】 missile.in 389 207 155 300 299 170 158
4、65 【输出样例】missile.out6（最多能拦截的导弹数）2（要拦截所有导弹最少要配备的系统数）【参考程序】type node=record h,lens:word;end;var n,i,j,maxl,num,minsys:word; mis:arraywordof node; sysl:arraywordof word;begin assign(input,missile.in);reset(input); assign(output,missile.out);rewrite(output); while not eoln do begin inc(n); read(misn.h);
5、 misn.lens:=1; end; for i:=2 to n do beginfor j:=1 to i-1 do if(misj.hmisi.h)and(misj.lens+1misi.lens) thenmisi.lens:=misj.lens+1;if misi.lensmaxl then maxl:=misi.lens; end; writeln(maxl); num:=1; sysl0:=maxint; sysl1:=mis1.h; for i:=2 to n do begin minsys:=0;for j:=1 to num doif(syslj=misi.h)and(sy
6、slj0)and(aj.dismaxint)and(aj.dis+mapi,jai.dis)then while ai do begin dis:=aj.dis+mapi,j; pre:=j; end; writeln(dis=,a1.dis); x:=1; while ax.pre0 do begin write(x, ); x:=ax.pre; end; writeln(x); close(output);end.4、挖地雷（Mine.pas）在一个地图上有N个地窖（N=200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的。某人可以从任一处开始挖地雷，
7、然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。【输入格式】N 地窖的个数W1，W2，WN 每个地窖中的地雷数X1，Y1 表示从X1可到Y1X2，Y20 ，0 表示输入结束【输出格式】K1K2Kv 挖地雷的顺序MAX 最多挖出的地雷数【输入样例】Mine.in65 10 20 5 4 51 21 42 43 44 54 65 60 0【输出样例】Mine.out3-4-5-634【参考程序】var n,start:byte; w:array1.200of word; g:array1.200,1.200of boolean;
8、f:array1.200of longword; next:array1.200of byte; max:longword;procedure init;var i,x,y:byte;begin assign(input,mine.in);reset(input); readln(n); for i:=1 to n do read(wi); readln; readln(x,y); fillchar(g,sizeof(g),false); while(x0)and(y0)do begin gx,y:=true; readln(x,y); end; close(input);end;initpr
9、ocedure work;var i,j:byte;begin fillchar(f,sizeof(f),0); fn:=wn; fillchar(next,sizeof(next),0); for i:=n-1 downto 1 do begin for j:=i+1 to n do if(gi,j)and(fjfi)then begin fi:=fj; nexti:=j; end; inc(fi,wi); end; max:=0; for i:=1 to n do if fimax then begin max:=fi; start:=i; end;end;workprocedure print;begin assign(output,mine.out);rewrite(output); write(start); while nextstart0 do begin
