动态规划题目及其代码

动态规划题目及其代码ByLYLtim1、数塔问题(tower.pas)

设有一个三角形的数塔，如下图所示。顶点结点称为根结点，每个结点有一个整数数值。从顶点出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。

【样例输入】tower.in

5

{数塔层数}

13

11

8

12

7

26

6

14

15

8

12

7

13

24

11

【样例输出】tower.out

max=86

【参考程序】usesmath;

varn,i,j:byte;

a:array[1..10,1..10]ofword;

f:array[1..10,1..10]ofword;

begin

assign(input,'tower.in');reset(input);

assign(output,'tower.out');rewrite(output);

readln(n);

fori:=1tondo

begin

forj:=1toido

read(a[i,j]);

readln;

end;

fillchar(f,sizeof(f),0);

fori:=1tondof[n,i]:=a[n,i];

fori:=n-1downto1do

forj:=1toido

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

38920715530029917015865

【输出样例】missile.out

6（最多能拦截的导弹数）

2（要拦截所有导弹最少要配备的系统数）

【参考程序】typenode=record

h,lens:word;

end;varn,i,j,maxl,num,minsys:word;

mis:array[word]ofnode;

sysl:array[word]ofword;begin

assign(input,'missile.in');reset(input);

assign(output,'missile.out');rewrite(output);

whilenoteolndo

begin

inc(n);

read(mis[n].h);

mis[n].lens:=1;

end;

fori:=2tondo

begin

forj:=1toi-1do

if(mis[j].h>mis[i].h)and(mis[j].lens+1>mis[i].lens)

then

mis[i].lens:=mis[j].lens+1;

ifmis[i].lens>maxl

thenmaxl:=mis[i].lens;

end;

writeln(maxl);

num:=1;

sysl[0]:=maxint;

sysl[1]:=mis[1].h;

fori:=2tondo

begin

minsys:=0;

forj:=1tonumdo

if(sysl[j]>=mis[i].h)and(sysl[j]<sysl[minsys])

K1——K2——……——Kv

{挖地雷的顺序}

MAX

{最多挖出的地雷数}

【输入样例】Mine.in

6

51020545

12

14

24

34

45

46

56

00

【输出样例】Mine.out

3-4-5-6

34

【参考程序】varn,start:byte;

w:array[1..200]ofword;

g:array[1..200,1..200]ofboolean;

f:array[1..200]oflongword;

next:array[1..200]ofbyte;

max:longword;procedureinit;

vari,x,y:byte;

begin

assign(input,'mine.in');reset(input);

readln(n);

fori:=1tondoread(w[i]);

readln;

readln(x,y);

fillchar(g,sizeof(g),false);

while(x<>0)and(y<>0)do

begin

g[x,y]:=true;

readln(x,y);

end;

close(input);

end;{init}procedurework;

vari,j:byte;

begin

fillchar(f,sizeof(f),0);

f[n]:=w[n];

fillchar(next,sizeof(next),0);

fori:=n-1downto1do

begin

forj:=i+1tondo

if(g[i,j])and(f[j]>f[i])then

begin

f[i]:=f[j];

next[i]:=j;

end;

inc(f[i],w[i]);

end;

max:=0;

fori:=1tondo

iff[i]>maxthen

begin

max:=f[i];

start:=i;

end;

end;{work}procedureprint;

begin

assign(output,'mine.out');rewrite(output);

write(start);

whilenext[start]<>0do

begin

write('-',next[start]);

start:=next[start];

end;

writeln;

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(1<=N<=5000)，表示分布在河两岸的城市对数。接下来的N行每行有两个由空格分隔的正数C，D（C、D〈=x〉，描述每一对友好城市与河起点的距离，C表示北岸城市的距离而D表示南岸城市的距离。在河的同一边，任何两个城市的位置都是不同的。

【输出格式】

输出文件(ship.out)：要在连续的若干行里给出每一组数据在安全条件下能够开通的最大航线数目。

【输入输出样例】Ship.in30

454

52

45

21

33

1Ship.out3【参考程序】typenode=recordc,d,l:word;end;varx,n:word;

y:longword;

a:array[1..5000]ofnode;

maxl:word;procedureinit;

vari:word;

begin

assign(input,'ship.in');reset(input);

readln(x,y);

readln(n);

fori:=1tondo

witha[i]do

begin

readln(c,d);

l:=1;

end;

close(input);

end;{init}procedureqsort(l,r:word);

varpl,pr,m:word;

t:node;

begin

pl:=l;pr:=r;m:=a[(l+r)>>1].c;

repeat

whilea[pl].c<mdoinc(pl);

whilea[pr].c>mdodec(pr);

ifpl<=prthen

begin

t:=a[pl];a[pl]:=a[pr];a[pr]:=t;

inc(pl);dec(pr);

end;

untilpl>pr;

ifpl<rthenqsort(pl,r);

ifpr>lthenqsort(l,pr);

end;{qsort}procedurework;

vari,j:word;

begin

fori:=2tondo

begin

forj:=1toi-1do

if(a[j].d<a[i].d)and(a[j].l+1>a[i].l)thena[i].l:=a[j].l+1;

ifa[i].l>maxlthenmaxl:=a[i].l;

end;

end;{work}procedureprint;

begin

assign(output,'ship.out');rewrite(output);

writeln(maxl);

close(output);

end;{print}begin{main}

init;

qsort(1,n);

work;

print;

end.7、砝码称重(weight.pas)

设有1g，2g，3g，5g，10g，20g的砝码各若干枚（其总重≤1000g），要求：

【输入格式】

a1a2a3a4a5a6(表示1g砝码有a1个，2g砝码有a2个，....20g砝码有a6个)

【输出格式】

Total=N(N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况)

【输入样例】weight.in

110

0

0

0

【输出样例】weight.out

Total=3，表示可以称出1g，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;

begin

assign(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:=1to6do

forj:=1tow[0]do

fork:=1ton[i]do

begin

nw:=w[j]+wt[i]*k;

ifnotvis[nw]then

begin

vis[nw]:=true;

inc(w[0]);

w[w[0]]:=nw;

end;

end;

writeln('Total=',w[0]-1);

close(input);close(output);

end.8、装箱问题(boxes.pas)

有一个箱子容量为v（正整数，0≤v≤20000），同时有n个物品（0<n≤30），每个物品有一个体积（正整数）。要求从n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

【输入格式】

箱子的容量v

物品数n

接下来n行，分别表示这n个物品的体积

【输出格式】

箱子剩余空间

【输入样例】boxes.in

24

6

8

3

12

7

9

7

【输出样例】boxes.out

0

【参考程序】varv,j,cost:word;

n,i:byte;

c:array[1..30]ofword;

f:array[0..20000]ofboolean;

begin

assign(input,'boxes.in');reset(input);

assign(output,'boxes.out');rewrite(output);

readln(v);

readln(n);

fori:=1tondoreadln(c[i]);

close(input);

fillchar(f,sizeof(f),false);

f[0]:=true;

fori:=1tondo

forj:=vdowntoc[i]do

iff[j-c[i]]thenf[j]:=true;

cost:=v;

whilenotf[cost]dodec(cost);

writeln(v-cost);

close(output);

end.9、合唱队形（Chorus.pas）

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2,…,K，他们的身高分别为T1,T2,…,TK，则他们的身高满足T1<T2<…<Ti,Ti>Ti+1>…>TK(1≤i≤K)。

已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

【输入文件】

输入文件chorus.in的第一行是一个整数N（2≤N≤100），表示同学的总数。第二行有n个整数，用空格分隔，第i个整数Ti（130≤Ti≤230）是第i位同学的身高（厘米）。

【输出文件】

输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

【样例输入】chorus.in

8

186186150