旅游预算

一个旅行社需要估算乘汽车从某城市到另一城市的最小费用，沿路有若干加油站，每个加油站收费不一定相同。

旅游预算有如下规则：

若油箱的油过半，不停车加油，除非油箱中的油不可支持到下一站；每次加油时都加满；在一个加油站加油时，司机要花费2元买东西吃；司机不必为其他意外情况而准备额外的油；汽车开出时在起点加满油箱；计算精确到分（1元=100分）。编写程序估计实际行驶在某路线所需的最小费用。

输入格式：

从当前目录下的文本文件“route.dat”读入数据。按以下格式输入若干旅行路线的情况：

第一行为起点到终点的距离（实数）

第二行为三个实数，后跟一个整数，每两个数据间用一个空格隔开。其中第一个数为汽车油箱的容量（升），第二个数是每升汽油行驶的公里数，第三个数是在起点加满油箱的费用，第四个数是加油站的数量。（〈=50）。接下去的每行包括两个实数，每个数据之间用一个空格分隔，其中第一个数是该加油站离起点的距离，第二个数是该加油站每升汽油的价格（元/升）。加油站按它们与起点的距离升序排列。所有的输入都有一定有解。

输出格式：

答案输出到当前目录下的文本文件“route.out”中。

该文件包括两行。第一行为一个实数和一个整数，实数为旅行的最小费用，以元为单位，精确到分，整数表示途中加油的站的N。第二行是N个整数，表示N个加油的站的编号，按升序排列。数据间用一个空格分隔，此外没有多余的空格。

输入输出举例：

海上交通控制

海上交通图可以用一个有向图来表示，顶点表示港口，边表示两个港口之间是否有航线可通。为保证海上交通安全和以尽量快的速度到达目的地，每艘船在出发前都将航行计划（包括出发时间、速度、出发与到达港口）提交给海上交通控制局，由海上交通控制局为它们制定航线。现给出一系列的船只航行计划（包括出发时间、速度、出发与到达港口），请你根据以下原则编程为它们制定航线：

1、每艘船在出发的一瞬间提交航行计划（提交和出发的时间差可以忽略）；

2、每艘船都严格按照出发时间出发，不能提前，也不能延迟；

3、在任何时间一条航道（两港口间的直达航线）上只能有一艘船，因此，一艘船在出发的瞬间发现某航道将在末来的某段时间内会被在它之前出发的船占用，则它在那一段时间内将不会使用该航道，当然其余时间还是可以使用该航道；

4、每个港口均可被无限艘船同时使用；

5、在满足上述条件后，要使本船航行的时间最短；

6、假如某船不能到达目标港口，那么它将放弃这个航程；

7、船在任何时候都不能停下来，即从出发后，要一直航行到目的地，中途不得在航道或港口中停留。

时间用4位数字表示如2345表示23：45，速度单位用节（海里/小时）表示。在计算时间时，中间结果应是精确的时间（即不要四舍五入到分钟），而航行时间的计算是以总距离除以速度为准，最终到目标地的时刻应是航行时刻加上航行时间的四舍五入到分钟的结果。

输入格式：

从当前目录下的文本文件“LANE.DAT”读入数据。输入的数据一定有解，且不会出现跨越00：00的情况，例如，一艘船在23：55出发，第二天0：15到达的情况是不会出现的。输入文件开头是港口定义：

第一行是港口数N（〈=26）；

第二行是一个长度为N的大写字母串，每个字母表示一个港口名字；

第三行开始N行的N X N矩阵是一个邻接矩阵，每行有N个整数，其值为港口间距离（单位为海里），整数间以空格分隔（若为0表示两港口没有直达航线相连）；

接着的一行是一个整数M（〈=50），表示共有M艘船提交航行计划；

接下去的每3行表示一艘船的航行计划，其中第一行是船名，第二行是出发时间和航速，两者均为整数，以一个空格分隔，第三行是两个大写安母，之间没有任何分隔，第一个表示出发的港口，第二个表示目的港口；

输出格式：

答案输出到当前目录下的文本文件“LANE.OUT”中。该文件的每3行表示一艘船的航线，其中第一行是船名，第二行是出发时间和到达时间，两者均为整数，以一个空格分隔，第三行是数个大写字母，之间没有任何分隔，表示该船经过的港口（包括出发和目的港口）。如果这艘船放弃航程时，到达时间用－１来表示，并留空第三行。

注意：在输入和输出中航行计划和航线均按出发时间排序，时间精确到分钟。

输入输出举例：

防卫导弹

一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型 防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下列两个条件之一：

1、它是该次测试中第一个被防卫导弹截击的导弹；

2、它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹。

输入格式：

从当前目录下的文本文件“CATCHER.DAT”读入数据。该文件的第一行是一个整数N（0〈=N〈=4000），表示本次测试中，发射的进攻导弹数，以下N行每行各有一个整数hi（0〈=hi〈=32767），表示第i个进攻导弹的高度。文件中各行的行首、行末无多余空格，输入文件中给出的导弹是按发射顺序排列的。

输出格式：

答案输出到当前目录下的文本文件“CATCHER.OUT”中，该文件第一行是一个整数max，表示最多能截击的进攻导弹数，以下的max行每行各有一个整数，表示各个被截击的进攻导弹的编号（按被截击的先后顺序排列）。输出的答案可能不唯一，只要输出其中任一解即可。

输入输出举例：

求函数最大值

已知3个函数A，B，C值如下表示，自变量取值为0----10的整数。请用动态规划的方法求出一组x，y，z，使得A(x)+B(y)+C(z)为最大，并且满足x²+y²+z²<N，N由键盘输入。-