动态规划题目及其代码ByLYLtim1、数塔问题(tower.pas)设有一个三角形的数塔，如下图所示。顶点结点称为根结点，每个结点有一个整数数值。从顶点出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。【样例输入】tower.in5{数塔层数}1311812726614158127132411【样例输出】tower.outmax=86【参考程序】usesmath;varn,i,j:byte;a:array[1..10,1..10]ofword;f:array[1..10,1..10]ofword;beginassign(input,'tower.in');reset(input);assign(output,'tower.out');rewrite(output);readln(n);fori:=1tondobeginforj:=1toidoread(a[i,j]);readln;end;fillchar(f,sizeof(f),0);fori:=1tondof[n,i]:=a[n,i];fori:=n-1downto1doforj:=1toidof[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j];writeln('max=',f[1,1]);close(input);close(output);end.2、拦截导弹(missile.pas)某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。【样例输入】missile.in38920715530029917015865【输出样例】missile.out6（最多能拦截的导弹数）2（要拦截所有导弹最少要配备的系统数）【参考程序】typenode=recordh,lens:word;end;varn,i,j,maxl,num,minsys:word;mis:array[word]ofnode;sysl:array[word]ofword;beginassign(input,'missile.in');reset(input);assign(output,'missile.out');rewrite(output);whilenoteolndobegininc(n);read(mis[n].h);mis[n].lens:=1;end;fori:=2tondobeginforj:=1toi-1doif(mis[j].h>mis[i].h)and(mis[j].lens+1>mis[i].lens)thenmis[i].lens:=mis[j].lens+1;ifmis[i].lens>maxlthenmaxl:=mis[i].lens;end;writeln(maxl);num:=1;sysl[0]:=maxint;sysl[1]:=mis[1].h;fori:=2tondobeginminsys:=0;forj:=1tonumdoif(sysl[j]>=mis[i].h)and(sysl[j]<sysl[minsys])thenminsys:=j;ifminsys=0thenbegininc(num);sysl[num]:=mis[i].h;endelsesysl[minsys]:=mis[i].h;end;writeln(num);close(input);close(output);end.3、最短路径（short.pas）在下图中找出从起点到终点的最短路径。【样例输入】short.in70350000000786000004500000004000000700000060000000【样例输出】short.outminlong=141247【参考程序】typenode=recorddis,pre:word;end;varn,i,j,x:byte;map:array[byte,byte]ofword;a:array[word]ofnode;beginassign(input,'short.in');reset(input);assign(output,'short.out');rewrite(output);readln(n);fori:=1tondobegina[i].dis:=maxint;forj:=1tondoread(map[i,j]);end;close(input);a[n].dis:=0;fori:=n-1downto1doforj:=ndowntoi+1doif(map[i,j]>0)and(a[j].dis<maxint)and(a[j].dis+map[i,j]<a[i].dis)thenwhilea[i]dobegindis:=a[j].dis+map[i,j];pre:=j;end;writeln('dis=',a[1].dis);x:=1;whilea[x].pre<>0dobeginwrite(x,'');x:=a[x].pre;end;writeln(x);close(output);end.4、挖地雷（Mine.pas）在一个地图上有N个地窖（N<=200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。【输入格式】N{地窖的个数}W1，W2，……WN{每个地窖中的地雷数}X1，Y1{表示从X1可到Y1}X2，Y2……0，0{表示输入结束}【输出格式】K1——K2——……——Kv{挖地雷的顺序}MAX{最多挖出的地雷数}【输入样例】Mine.in6510205451214243445465600【输出样例】Mine.out3-4-5-634【参考程序】varn,start:byte;w:array[1..200]ofword;g:array[1..200,1..200]ofboo...