动态规划题目及其代码

精品文档你我共享AAAAAA动态规划题目及其代码ByLYLtim1、数塔问题(tower.pas)设有一个三角形的数塔，如下图所示。顶点结点称为根结点，每个结点有一个整数数值。从顶点出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。13118127266141512713【样例输出】tower.out824tower.in｛数塔层数｝【样例输入】115max=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]);readIn;end;fillchar(f,sizeof⑴,0);fori:=1tondof[n,i]:=a[n,i];fori:=n-1downto1doforj:=1toidof[i,j]:=max(f[i+1』,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;writeIn(maxi);num:=1;sysl[0]:=maxint;sysl[1]:=mis[1].h;fori:=2tondobeginminsys:=0;forj:=1tonumdoif(sysl[j]>=mis[i].h)and(sysl[j]vsysl[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.inshort.out【样例输入】70350000000786000004500000004000000700000060000000【样例输出】miniong=14247【参考程序】typenode=recorddis,pre:word;end;精品文档你我共享0,AAAAAAvarn,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-1downto1forj:=ndodowntoi+1doif(map[i』>0)and(a[j].disvmaxint)and(a[j].dis+map[i,j]va[i].dis)thenwhilea[i]dobegindis:=a[j].dis+map[i,j];pre:=j;end;writeln('dis=',a[1].dis);x:=1;whilea[x].prev>0dobeginwrite(x,'');x:=a[x].pre;end;writeIn(x);close(output);end.4、挖地雷(Mine.pas)在一个地图上有N个地窖给出地窖之间的连接路径，雷，然后沿着指出的连接往下挖(仅能选择一条路径)，当无连接时挖地雷工作(Nv=200,每个地窖中埋有一定数量的地雷。同时，并规定路径都是单向的。某人可以从任一处开始挖地结束。设计一个挖地雷的 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，使他能挖到最多的地雷。【输入格式】N｛地窖的个数｝W1XI，X2,W2……WNY1Y2｛每个地窖中的地雷数｝｛表示从X1可到丫1｝0【输出格式】｛表示输入结束｝精品文档你我共享AAAAAAKv｛挖地雷的顺序｝｛最多挖出的地雷数｝K1——K2——……——MAX【输入样例】Mine.in65102054512TOC\o"1-5"\h\z44456600【输出样例】Mine.out3-4-5-634【参考程序】varn,start:byte;w:array[1..200]ofword;g:array[1..200,1..200]ofboolean;f:array[1..200]ofIongword;next:array[1..200]ofbyte;max:longword;Procedureinit;vari,x,y:byte;beginassign(input,'mine.in');reset(input);readln(n);fori:=1tondoread(w[i]);readln;readln(x,y);fillchar(g,sizeof(g),false);while(x<>0)and(yv>0)dobeging[x,y]:=true;readln(x,y);end;close(input);end;{init}procedurework;vari,j:byte;beginfillchar(f,sizeof(f),O);f[n]:=w[n];dofillchar(next,sizeof(next),0);fori:=n-1downto1beginforj:=i+1tondoif(g[i,j])and(f[j]>f[i])thenbeginf[i]:=f[j];next[i]:=j;end;inc(f[i],w[i]);end;max:=0;fori:=1tondoiff[i]>maxthenbeginmax:=f[i];start:=i;end;end;{work}procedureprint;beginassign(output,'mine.out');rewrite(output);write(start);whilenext[start]<>0dobeginwriteC-',next[start]);start:=next[start];end;writeIn;writeln(max);close(output);end;{print}begin{main}init;work;print;end.5、轮船问题(ship.pas)【问题描述】某国家被一条河划分为南北两部分，在南岸和北岸总共有N对城市，每一城市在对岸都有唯一的友好城市，任何两个城市都没有相同的友好城市。每一对友好城市都希望有一条航线来往，于是他们向政府提出了申请。由于河终年有雾。政府决定允许开通的航线就互不交叉(如果两条航线交叉，将有很大机会撞船)。兴建哪些航线以使在安全条件下有最多航线可以被开通。【输入格式】输入文件(ship.in):包括了若干组数据，每组数据格式如下：第一行两个由空格分隔的整数X，y，10<=x〈=6000,10〈=y〈=100。x表示河的长度而y表示宽。第二行是一个整数N(1v=Nv=5000)表示分布在河两岸的城市对数。接下来的N行每行有两个由空格分隔的正数C,D(C、D〈=x>，描述每一对友好城市与河起点的距离，C表示北岸城市的距离而D表示南岸城市的距离。在河的同一边，任何两个城市的位置都是不同的。【输出格式】输出文件(ship.out):要在连续的若干行里给出每一组数据在安全条件下能够开通的最大航线数目。【输入输出样例】Ship.in30Ship.out【参考程序】typenode=recordc,d,l:word;end;varx,n:word;y:longword;a:array[1..5000]ofnode;maxl:word;procedureinit;vari:word;beginassign(input,'ship.in');reset(input);readln(x,y);readln(n);fori:=1tondowitha[i]dobeginreadIn(c,d);l:=1;end;close(input);end;{init}procedureqsort(l,r:word);varpI,pr,m:word;t:node;beginpl:=l;pr:=r;m:=a[(l+r)>>1].c;repeatwhilea[pl].cvmdoinc(pI);whilea[pr].c>mdodec(pr);ifplv=prthenbegint:=a[pl];a[pl]:=a[pr];a[pr]:=t;inc(pl);dec(pr);end;untilpl>pr;ifplvrthenqsort(pl,r);ifpr>lthenqsort(l,pr);end;{qsort}procedurework;vari,j:word;beginfori:=2tondobeginforj:=1toi-1doif(a[j].da[i].l)thena[i].l:=a[j].l+1;ifa[i].l>maxlthenmaxl:=a[i].l;end;end;{work}procedureprint;beginassign(output,'ship.out');rewrite(output);writeIn(maxi);close(output);end;{print}begin{main}init;qsort(1,n);work;print;end.7、砝码称重（weight.pas）设有1g,2g,3g,5g,10g,20g的砝码各若干枚（其总重wlOOOg）,要求：【输入格式】a1a2a3a4a5a6（表示1g砝码有a1个，2g砝码有a2个，....20g砝码有a6个）【输出格式】TotaI=N（N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）weight.in00weight.out【输入样例】1100【输出样例】Total=3，表示可以称出1g,2g,3g三种不同的重量【参考程序】constwt:array[1..6]ofshortint=(1,2,3,5,10,20);varn:array[1..6]ofword;vis:array[0..1000]ofboolean;w:array[0..1000]ofword;i,j,k,nw:word;beginassign(input,'weight.in');reset(input);assign(output,'weight.out');rewrite(output);fillchar(vis,sizeof(vis),false);fori:=1to6doread(n[i]);w[0]:=1;w[1]:=0;fori:=1to6doforj:=1tow[0]dofork:=1ton[i]dobeginnw:=w[j]+wt[i]*k;ifnotvis[nw]thenbeginvis[nw]:=true;inc(w[O]);w[w[O]]:=nw;end;end;writeln('Total=',w[0]-1);close(input);close(output);end.8、装箱问题（boxes.pas）有一个箱子容量为v（正整数，0Wv<20000）,同时有n个物品（0Ti+1>…>TK(1stu[i].ups)thenstu[i].ups:=stu[j].ups+1;fori:=n-1downto1doforj:=i+1tondoif(stu[j].hstu[i].downs)thenstu[i].downs:=stu[j].downs+1;max:=0;fori:=1tondoifstu[i].ups+stu[i].downs>maxthenmax:=stu[i].ups+stu[i].downs;writeln(n-max+1);close(output);end.沁园春•雪北国风光，里冰封，万里雪望长城内外，惟余莽莽大河顿失滔滔。山舞银蛇,原驰蜡象,欲与天公试比高。须晴日,看红装素裹,分外妖娆。江山如此多娇,引无数英雄竞折腰。惜秦皇汉武，略输文采；唐宗宋祖，稍逊风骚。•代天骄，成吉思汗，只识弯弓射大雕。俱往矣，数风流人物，还看今朝。U-克