动态规划题目及其代码

1、动态规划题目及其代码作者:日期:动态规划题目及其代码 By LY L t im1、数塔问题（tower.pas ） ?设有一个三角形的数塔,如下图所示。顶点结点称为 根结点,每个结点有一个整数数值。从顶点出发，在每一结点可以选择向左走或是 向右走，一起走到底层，要求找出一条路径，使路径上的值最大。【样例输入】towe51128?1 27r .i n数塔层数13?726 6?13241158?1【样例输出】m ax=86【参考程序】tow e r.outuse s math;a:arr?va r n, i ,j:byte ;ay1.110 ,1 . .10 o f word;b e ginass

2、ig n( a ssig r e adli n put ,' n ( o utput, n (n); ?e nd;f illchar ( f ,sii := an,i ;?for j:=1 twr it eln ('max=' ut p u t) ; ?3n d .0 ,1 .10 of wo r d;?to wer.i n')； r ese t(i npu t);'towe r . o u t，); r ew rite(o fo r i : = 1 to n do ?f o r j := 1 to i d o read(a e adin;z e o f

3、(f),for i:o i f i ,j:,f C1,i）；0 ); ?=n - 1d o=max(fi+1 , j , fi+1 ) ; ?c lo s e(ifor i:=1 dow nto 1 dou t p u t);b eg it o n do f n,1 , J +1)+ai ，j; n pu t );clo s e( oa s)?某国为了防御敌国的导弹袭击，发展出一2、拦截导弹（mi s sile.p种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够 到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天 ，雷达捕 捉到敌国的导弹来袭。由于该系统还在试

4、用阶段，所以只有一套系统 ，因此有可 能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）,计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套 这种导弹拦截系统。？【样例输入】 mi s sile.i n38 9 207 1 5 5 300 29 91 701 5 8 65【输出样例】mis s ile.o ut6（最多能拦截的导弹数）2 （要拦截所有导弹最少要配备的系统数）？【参考程序】ty pehnode= recor d,1 ens： word; en d;,i ,j , maxi , n um,m in mis:sa rr a y

5、word o f no sl:array wordofS ys: wor d; de ;word;beg in ?s sign(ou t eolnassig n(i npu t,'missi put ,'m id ossi 1 e.ou t1');e.i n ');reset( in put) ; ? re write(out put); ?awhile noinc(n); ?n . h); ? forread(mi s misn . lns:=1; ?end ;f( m is j.h the ni:=2 bI > mis mi si if misi t

6、en=1；:s:=0; ?n doto gi n?i .h ).lens :.1eo i-1 d o?fo r j:=1 ta n d(m is j . l en s+ 1 >mi s i=m isj.1e ns+ 1;n s>maxlh en m axl: = mi s i .lens; d ;?write 1 n(max1 );i.l en s)?nu m:s y s l0 s l1: i:=2syfor:=ma x i nt; =mi s1.t o n d begi n?for j : = 1if( sy s 1j : >=m isimins yt o num d o.

7、h) a nd(sysl j <s ys lmi nst hen m ins ys :=j;i f m in sys=0 the nend?nd;?begi n in c(n u m); sy s lnum := m isi.h e 1 s e sys lminsys : =mi s i.h;?w ri t eln (num);1 o se(i npu t);clos e(out p u t) ; ?e nd.3、最短路径(sh o r t .pa s) ?在下图中找出从起点到终点的最短路径。7035 00 0 0 0 0 0 0 0 0 程序】04 0 0 0?0 0?【样例输出】0

8、0?0 7 8600 0 0? 0 4 5 00 7 0 0 0 0?0 0 6I s ho rt.ou t ?mi nl o ng= 1 44 2 1? 7?【参考typed ;?node= record ?end ;dis,pr e: worvar n,i , J, x: byt e ;?o f node;a:array wo rdbeg in ?as s ig n ( as s i g n( o utpu re adl n (n); ? beg in ?t;e n d; close(i npu t);a n .d is : f o r i ：= n1 f o r j: (aj : .di

9、s < maxi nt) a e a i w rit ew hi l j; end; ?whilex : . p re; ? clo smap:arr a y by t e, b yteof wo r d;i n pu t , / sh o rt . t ,'sh ort.out') fo ri:=1 tn ');resetwritedaoifo rj:=1do(inpu t);(output )；.dis : = max i nad(map i ,J )；=0;d ow=nnto 1d ownt o i+1 do ?f( m api, J >0) nd(a

10、j . d is + mapi,jva i .d i s)t do b egi n d is:= aj .dis+ m ap i,j;1 n('a x. prev>0 d writ ed i s=/ ,a1.dis o?e (x,'/ ); ?n d; ?wr i);?beg inandhe np re :=1;X := at eln (x);e(output) ; ?3n d .4、挖地雷（Mi n e.pas）在一个地图上有N个地窖（NV =200）,每个地窖中埋有一定数量的地雷。同时, 给出地窖之间的连接路径，并规定路径都是单向的。某人可以从任一处开始挖地 雷,然后

11、沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结 束。设计一个挖地雷的方案，使他能挖到最多的地雷。【输入格式】N 地窖的个数?W1,W2,WN每个地窖中的地雷数?X 1, Y1表示从X1可到丫1 X2, Y2 0? , 0表示输入结束?【输出格式】?K1 K 2K v 挖地雷的顺序MAX最多挖出的地雷数?【输入样例】Mine.i n 6?5 1 0 20 5 41 2 1? 42 43 45?4 5 4? 6 60 0Mine, o ut5-4- 3?6【输出样例】34?【参考程序】v a r n , st a rt: b yte ; w:array1.200 of w o r

12、d;g:arra y 1.200 , 1 . 2 00of boo 1 ea n; ? f:array0o f b yte; ?1 . . 200of lo max:long wong wo rd; ?d ;n e x t :array 1. .2 0procedur ev ar i , X,begi na ssIt ； by te;i g n (input , 'mine.in' ?readln(n ) ;?ad(w i ); ?s ize of (g),while(x<close(en d ; i nit r ea d f alse);>0 ) an begin

13、 ?rn d;n put);fo r1 n;?);reset(i ni := 1 to nreadln (x,y); ?d( y<> 0 )doea dln (x, y);p r oce d ur e w ova rr k;i , j : byte;P ut);d o r ef ill c har( g ,g x, y : = true;b egin?fillchar( f， sizeof(f ) ， 0);f n : = wn;f i ldownt o 1 dIc har(ne x t, s iz eo f( n ext), 0) ; ? o ?for i: =n o? en?

14、in ?b e gi nfor j : = i + 1i f(gto n di , j ) and(fj be g>f i) thindo?d； ?f fi bec (fi，wi );m ax:=0; ?> max th e ng in?i :；s tar t :=i;d; ?e nd ;work p roc e dure print; ?begin ? rewrite(o u t p ut) ; ?startv>0 dob eginwritef i : n ex t e nd;for i: =1=fjto nma x:= fassi g n( ou t p ut,'

15、min e .out'); w rite(s t art); ?w hile n exttart : ) ;?t; ?close(outen d; pr in te n d; ?pu t);('-'，n ex t sst art: = n e x t s t ar w rit e l n ; ?w ri teln (ma x);work; ?print;begi nm ain ? end.5、轮船问题(s h ip.pas)【问题描述】,每一城市在 每一对友好城某国家被一条河划分为南北两部分，在南岸和北岸总共有N对城市 对岸都有唯一的友好城市，任何两个城市都没有相同的友

16、好城市。市都希望有一条航线来往，于是他们向政府提出了申请。由于河终年有雾。政府 决定允许开通的航线就互不交叉(如果两条航线交叉，将有很大机会撞船)。兴 建哪些航线以使在安全条件下有最多航线可以被开通。【输入格式】？输入文件(shi p . in):包括了若干组数据,每组数据格式如下:?第一行两个由空格分隔的整数 x,y,1 0< =x=6000, 1 0 = y=100。x表示河的长度而y表示宽。第二行是一个整数N ( 1 <=N< = 500 0 ), 表示分布在河两岸的城市对数。接下来的 N行每行有两个由空格分隔的正数 C, D(C、D =x> ,描述每一对友好城市

17、与河起点的距离,C表示北岸城市的距离 而D表示南岸城市的距离。在河的同一边，任何两个城市的位置都是不同的。【输出格式】？输出文件(S hip. ou t):要在连续的若干行里给出每一组数据在安全条件下能够开通的最大航线数目。【输入输出样例】S hip. inShip. o u t【参考程序】type n ode =reco r d c,d, l : wo rd; end;var x, n :word;y: l o ngw ord;a:array1 . . 50 00 ofno de;?maxl:word;proced u r e in i t; var i:wo r d;?b egin ass

18、ig n(x, y ); ?(i n put , readl n( with'shi p.n) ;?i d obegi n ?);r es e t(input for i:=1 t o);? n d or e adlnrea dln(c , d); ?en d; ?l: =1 ;c1os e1 npu);?end; in itprd e;begioc edur e qsort(l,r:w o rd); ?v a r pl , p r.m:wo rd; ?t:non ?p 1 :=l;r ep eat ?(pl ) ;?pr := r; m =a (l+r)>>1. w h

19、i le apl.c w h i le a pr.c>m d oc ;< m d o in cd e c( p r);p 1 vr the n qso if pr >l the n qsort end ;qsortr t(pl,r);(1 ,p r );P r ocedure w ork; ?va r i, do?beg in ?j :word; ?3eg in ?if(i .l ) t h en a i .l : =a j.1i f a i. en d;?end ;worka j.d<ai.d)and+ l ;1 >max l the nfor i:=2for

20、j:=1 to (aj :toni-1 d o.l + l>amaX l:=a1 . 1 ；if plv = pr the nb eg int:=apl;apl := a pr;a p r:=t;in c (pl);dec(pr);en d;u n t i l pl > p r ;i fassi g n(output,' i teln(maxi) ； ?s h ip. out / ) ;r cl o s e (o u t pp roce d ure pr int; ?b egi n ? e wri te( outp u t) ; ?w rut); ?3 n d;printw

21、 ork;b eg i n mai n in it;q s o rt( l ,n); ? p rin t;e n d.7、砝码称重（w eight .pa s ）设有l g, 2g,3 g,5g,1 0 g, 2 0g的砝码各若干枚（其总重w 1000g）,要求:?【输入格式】?a1 a2 a3 a4 a5 a 6 （表示1 g砝码有a1个,2g砝码有a2个,.2 0g砝码有a6个）？【输出格式】Tot a l=N （N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不 用的情况）【输入样例】W eight.in1 1 0000?【输出样例】we ight . outTo t al =

22、 3,表示可以称出1g, 2 g,3g三种不同的重量【参考程序】co n st wt : arr a y1 . .6 o f s h ort var n : array 1. 6o f word;V is: a rray 0. .1000 of0.1000o f word ;i ,j,k , nw word; ?be gin ?n ') ; r e se t (input);in t=(1,bo o leaas2 ,3 , 5,10,20 );w:ar r ays ign (i np u t ,'we i ght. ia s sign(output , ' w e i

23、gh t .out');rewrit e (out p ut);fi 1 Ichar (vi read (n i ); ?fo r i:=1 to 6n w:=w j+wt i *k; if not vin w;?d;?w 0 卜1 );close(i n put);e nd; ?sn w th en begi nvis n w:=truin c(w0);w w 0:=e nw rit e I n ('Total ='c Io s e(ou t put) ; ?e nd.fo r i:=1 to 6 dos , s izeof(vis) , fa 1 se); ?w 0

24、 : =1;w 1 := 0 ;do ?f or j : =1 t o w 0 dof o r k := 1 to ni dobegin8、装箱问题（bo xes. 有一个箱子容量为v（正整数， 每个物品有一个体积（正整数） 箱子的剩余空间为最小。【输入格式】 箱子的容量V?物品数p as）0< v< 2 0 0 0 0 ）,同时有 n 个物品（0vnW3 0）, 。要求从 n个物品中，任取若干个装入箱内，使接下来n行，分别表示这n个物品的体积？【输出格式】 箱子剩余空间【输入样例】box e s. i n246 8?3 ?12 7?97 ?【输出样例】b o xes. o ut

25、0?V ar v,j,cost: wo rd;n , i : by t e；c :arra y 1.30of w or d ;f:a r ray0.20 000 of booleat ,'boxes.i n');re set( in pu t);assi gn (output,'boxes.out');radln( V); ? read 1 n(n) ; ?i);? close( i nput)；f illcha r ( f ,sizeof (f) ,fals f 0: = true ;for i : =1 to n dof o r j:=vdownto cin

26、; ?begin ?assig n (in p ue wr ite(out p u t ); ?r efo r i ：= 1 t o n do read 1 n (cdo ?if f【参考程序】j-c i t h en f j : = tr u e;cost :=v; ?while not f c o st do d e c( c ost);writ e ln (v c ost); ?c l o se (o utpu t) ; ?3 n d.9、合唱队形(Cho r u s.pas) ?N位同学站成一排，音乐老师要请其中的(N-K) 位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形： 设K位同学从左到右依次编号为1,2,，K,他们的身高分别为T 1, T2,，T K,则他们的身高满足 T1 < T 2 < < Ti , Ti > Ti+1 > >< 2 3 0)是第i位同学的身高(厘米)。 t包括一行，这一行只包含一个整数，就TK (1 < i < K)o ?已知所有N位同学的身高，计算最少需要几位同学出列，可以 使得剩下的同学排成合唱队形。？【输入文件】？输入文件c ho r u s. i n的第一 行是一个整数N( 2 < N < 100)，表示同学的总数。第二行有n个整数，用 空格分隔