经典动态规划题集资料不课错过哦资源-CSDN文库

5星 · 超过95%的资源需积分: 10 145 浏览量 2008-08-28 15:21:32 上传评论 2 收藏 265KB DOC 举报

资源推荐

资源详情

资源评论

第十四章动态规划

1、数塔问题(tower.pas)

设有一个三角形的数塔，如下图所示。顶点结点称为根结点，每个结点有一个整数数值。从顶点出发

在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。

【样例输入】

数塔层数











【样例输出】



2、拦截导弹(missile.pas)

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然

它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到

敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于  的正整数），计算这套系统最多能拦

截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

【样例输入】 



【输出样例】

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

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

3、最短路径（short.pas）

在下图中找出从起点到终点的最短路径。

【样例输入】









1

7

4

3 8

6

7

5

4 6

5

6

V

1

V

2

V

3

V

4

V

5

V

6

V

7

【输入格式】

输入文件,-./包括了若干组数据，每组数据格式如下：

第一行两个由空格分隔的整数 ，0，〈〈，〈0〈。 表示河的长度而 0 表示

宽。第二行是一个整数 ,  .，表示分布在河两岸的城市对数。接下来的  行每行有两

个由空格分隔的正数 1，2（1、2〈〉，描述每一对友好城市与河起点的距离，1 表示北岸城市

的距离而 2 表示南岸城市的距离。在河的同一边，任何两个城市的位置都是不同的。

【输出格式】

输出文件,-.：要在连续的若干行里给出每一组数据在安全条件下能够开通的最大航线数目。

【输入输出样例】

3-















3-



6、骑士游历问题(knight.pas)

【详见教程】

7、砝码称重(weight.pas)

设有 ，，，，， 的砝码各若干枚（其总重≤），要求：

【输入格式】

,表示  砝码有  个， 砝码有  个， 砝码有  个.

【输出格式】

4, 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况.

【输入样例】



【输出样例】

4，表示可以称出 ，， 三种不同的重量

8、装箱问题(boxes.pas)

有一个箱子容量为 (（正整数，5(5），同时有  个物品（ 5），每个物品有一个

体积（正整数）。要求从  个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

【输入格式】

箱子的容量 (

物品数 

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

【输出格式】

箱子剩余空间

3

剩余36页未读，继续阅读

内容反馈

yiwaerdy

2012-10-22

非常齐全，非常多的DP题集，基本都给出了pascal代码！还是非常有用的

yahximusiz

粉丝: 0
资源: 1

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip