动态规划题目及其代码动态规题目及其代码动态规划题目及其代码动态规划题目及其代码.doc

动态规划题目及其代码 By LYLtim 1、数塔问题(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:array[1..10,1..10]of word;??? f:array[1..10,1..10]of word;begin??? assign(input,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(a[i,j]);??????????? readln;??????? end;??? fillchar(f,sizeof(f),0);??? for i:=1 to n do f[n,i]:=a[n,i];??? for i:=n-1 downto 1 do??????? for j:=1 to i do??????????? f[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.in???????????????????????? 389 207 155 300 299 170 158 65???? 【输出样例】missile.out6（最多能拦截的导弹数）2（要拦截所有导弹最少要配备的系统数）【参考程序】 type node=record?? h,lens:word;????end; var n,i,j,maxl,num,minsys:word;??? mis:array[word]of node;??? sysl:array[word]of word; begin??? assign(input,missile.in);reset(input);??? assign(output,missile.out);rewrite(output);??? while not eoln do??????? begin??????????? inc(n);??????????? read(mis[n].h);??????????? mis[n].lens:=1;??????? end;??? for i:=2 to n do??????? begin?????for j:=1 to i-1 do???? if(mis[j].hmis[i].h)and(mis[j].lens+1mis[i].lens) then???mis[i].lens:=mis[j].lens+1;?????if mis[i].lensmaxl  then maxl:=mis[i].lens;??????? end;??? writeln(maxl);??? num:=1;??? sysl[0]:=maxint;??? sysl[1]:=mis[1].h;??? for i:=2 to n do??????? begin????????? minsys:=0;?????????for j:=1 to num do???????if(sysl[j]=mis[i].h)and(sysl[j]sysl[minsys])