《动态规划模拟测试三》由会员分享，可在线阅读，更多相关《动态规划模拟测试三（4页珍藏版）》请在金锄头文库上搜索。
1、10049.加油问题题目类型：虚拟题目时间限制：1.0s空间限制：2.5MB一个美国旅行代理上经常被要求去估计开车从一个城市旅行至另一个城市的最小费用。他有 一个在通常路线上的大多数加油站的列表。列表包括了所有加油站的位置及当前每加仑汽油 的价格。为了简化估计费用的过程，代理商使用了以下的简化汽车驾驶员行为的规则：除非汽车无法用油箱里的汽油达到下一个加油站（如果有的话）或目的地，在油箱里还有不少于最大容量一半的汽油时，驾驶员从不在加油站停下来。在每一个停下的加油站，驾驶员总是将油加满。在一个加油站停下之后，驾驶员将为旅程在快餐和糖果上花去2.00元。在驶向加油站或目的地时，驾驶员不需要超过必须
2、量的汽油。不需要安全余量”。驾驶员开始旅行时油箱总是满的每个加油站付款时四舍五入到分（1元等于100分）。你必须写一个程序以估计驾驶员在旅程上至少要为汽油和食品付多少钱。输入格式开始的2行给出了出发地和目的地的信息。数据项的后继行代表了路线上的加油站，每个加油站用一行表示。下面是输入数据中数据项的精确格式及其含义。第一行：一个实数一一从出发地到目的地的距离（英里）第二行：三个实数及一个整数第一个实数是汽车油箱的最大的容量（加仑）第二个实数是汽车每加仑汽油可以行驶的英里数第三个实数是汽车在出发地城市加满油箱的费用（单位：元） 整数（小于51）是路线上加油站的数目接下来的每一行：两个实数第一个实数
3、是从出发地到加油站的距离（单位：英里）第二个实数是该加油站出售的汽油每加仑的价格（单位：分）数据项中的所有数据都是正的。一条路线上的加油站根据其到出发地的距离递增排列。路线上不存在这样的加油站，它到出发点的距离大于从出发点到目的地的距离。每条路线上 的加油站都被适当的安排以使得任何汽车都能从出发地开到目的地。输出格式仅一行，一个实数（保留两位小数），表示最小的花费（单位：元）。样例输入475.611.9 27.4 14.98 6102.0 99.9220.0 132.9256.3 147.9275.0 102.9277.6 112.9381.8 100.9样例输出27.3110050.对话题目
4、类型：虚拟题目时间限制：1.0s空间限制：2.5MB从前有两个人，一个名为one,另一个则叫puton。很奇怪，one除了称呼puton名字 夕卜，只对他说out和output两个单词;puton除了称呼one名字外，只对他说in和input 两个单词。最近人们在研究他们对话，但是，由于资料的混乱，其中可能有一些不是他们的对话。 你的任务是鉴别一些句子，判断这些句子是否可能是他们的对话。（即，判断句子是否可以 被划分成若干单词，这些单词只可以是on e、put on 、out、output、in和i nput）。输入n个字符串，长度不超过200,表示一句句子。如果可能是那两个人的对话，则输 出
5、”YES”；否则，输出”NO”。输入格式第一行一个整数n,表示一共有n句句子。此后每行一个字符串，表示一句句子。输出格式n行，每行一个”YES”或”NO”，表示你的判断结果。样例输入6puto ninon puti non eput oninin putoutoutputoneinin putwooutoutputoutpuutput样例输出YESNOYESNONONO10059.诸侯安置题目类型：虚拟题目时间限制：1.0s空间限制：2.5MB间圜讎】4覩如A前1有一尔强大的帝国，它册国土咸正菱形槪湎图22所示.4:齢国家有若干诸侯.由于这些诸侯都曾立下赫赫战功，国王淮爸给他们每人一块封地(正
6、方形. 中餉一制；但是，邃些诸侯女非常好战，当两聲诸侯位于同一存或同一列时场他们就会开战.如下图2 3齿n=3时钳国土，阴藏部芬表示诸侯所魁的位苴前两幅图中的诸侯可区互相攻击，第三幅则不可以川因此，他希望通过合理的安扫E诸侯国王自然不愿意看到他的诸侯们互相开战，致使国家动荡不安 所疑的位苣，悽他们两两之间都不能竣击.现在,给出正方形的辺长n段及需妾封地的诸侯数量k,要求懈求出所有可能的安貫方案数 k2n2-2m-l)由于行案数可能很多，你只雋要输出芳案数除辺5W的余数即可.*F输入】*仅一行，两牛整数n和匕中间用一空格隔开. 【输出】#个整鮫，表示方案数除回504的荼数 席例】*输入：.输出：223
