动态规划.docx

动态规划
相关知识：

动态规划

|

最短路径

|

复制书稿

|

车队过桥

|

石子
1、防卫导弹：
问题描述 ：一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型 防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下
列两个条件之一：
1、它是该次测试中第一个被防卫导弹截击的导弹；
2、它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹。
输入格式 ：从当前目录下的文本文件 ""读入数据 。该文 件的第一行是一个整数 N（0
=N〈=4000），表示本次测试中， 发射的进攻导弹数， 以下 N 行每行各有一个整数 hi（0〈=hi〈=32767），表示第 i 个进攻导弹的高度。文件中各行的行首、行末无多余空格，输入文件中给出的导弹是按发
射顺序排列的。
输出格式 ：答案输出到当前目录下的文本文件 ""中，该文件第一行是一个整数 max，表示最多能截击的进攻导弹数，以下的 max行每行各有一个整数，表示各个被截击的进攻导弹的编号（按被截击的先后顺序排列）。输出的答案可能不唯一，只要输出其中任一解即可。输入输出举例：
输 入 文 件 ：
输 出 文 件 ：
T

3
2
25
1
36
3
23
2、轮船 (Ships)
描述
有一个国家被一条何划分为南北两部分，在南岸和北岸总共有 N 个城镇，每一城镇在对岸都有唯一
的友好城镇。任何两个城镇都没有相同的友好城镇。每一对友好城镇都希望有一条航线来往。于是
他们向政府提出了申请。由于河终年有雾。政府决定不允许有任两条航线交叉（如果两条航线交叉，
将有很大机会撞船）。
你的任务是缟写一个程序来帮政府官员决定他们应拨款兴建哪些航线以使到没有出现交叉的航线最
多。
输入数据
输入文件（ ）包括了若干组数据，每组数据格式如下：
第一行两个由空格分隔的整数 x， y， 10〈 =x〈 =6000，10〈=y〈=100。 x 表示河的长度而 y 表示宽。
第二行是一个整数 N(1<=N<=5000)，表示分布在河两岸的城镇对数。 接下来的 N 行每行有两个由空格
分隔的正数 C， D（ C、D〈=x〉，描述每一对友好城镇沿着河岸与西边境线的距离， C 表示北岸城镇
的距离而 D 表示南岸城镇的距离。