动态规划练习题

最小乘车费用 (bus)

【问题描述】

假设某条街上每一公里就有一个公共汽车站，并且一种可能的乘车费用如下表：

公里数 费用 1 2 3 31 4 40 5 49 6 58 7 69 8 79 9 90 10 101 12 21

而任意一辆汽车从不行驶超过1 0公里。某人想乘车到达n公里远的地方，假设他可以任意次换车，请你帮他找到一种乘车方案，使得总费用最小。 注意：1 0公里的费用比1公里小的情况是允许的。 【输入文件】 共两行：

第一行为1 0个不超过200的整数，依次表示行驶1～1 0公里的费用，相邻两数间用一个空格隔开：

第二行为某人想要乘车的公里数(不超过20000的整数)。 【输出文件】

仅一行，包含一个整数，表示到达n公里所需要的最小费用。 【样例输入】

12 21 31 40 49 58 69 79 90 101 15

【样例输出】 147

船 (ships)

【问题描述】

PALMIA国家被一条河流分成南北两岸，南北两岸上各有N个村庄。北岸的每一个村庄有一个唯一的朋友在南岸，且他们的朋友村庄彼此不同。 每一对朋友村庄想要一条船来连接他们，他们向政府提出申请以获得批准。由于河面上常常有雾，政府决定禁止船只航线相交（如果相交，则很可能导致碰船）。 你的任务是编写一个程序，帮助政府官员决定批准哪些船只航线，使得不相交的航线数目最大。

【输入文件】ships.in

输入文件由几组数据组成。每组数据的第一行有2个整数X，Y，中间有一个空格隔开，X代表PALMIA河的长度（10<=X<=6000），Y代表河的宽度（10<=Y<=100）。第二行包含整数N，表示分别坐落在南北两岸上的村庄的数目（1<=N<=5000）。在接下来的N行中，每一行有两个非负整数C，D，由一个空格隔开，分别表示这一对朋友村庄沿河岸与PALMIA河最西边界的距离（C代表北岸的村庄，D代表南岸的村庄），不存在同岸又同位置的村庄。最后一组数据的下面仅有一行，是两个0，也被一空格隔开。 【输出文件】ships.out

对输入文件的每一组数据，输出文件应在连续的行中表示出最大可能满足上述条件的航

线的数目。 【输入样例】 30 4 7 22 4 2 6 10 3 15 12 9 8 17 17 4 2 0 0

【输出样例】 4

DOLLARS (dollars)

【问题描述】

在以后的若干天里戴维将学习美元与德国马克的汇率。编写程序帮助戴维何时应买或卖马克或美元，使他从100美元开始，最后能获得最高可能的价值。

【输入】

输入文件的第一行是一个自然数N，1≤N≤100，表示戴维学习汇率的天数。 接下来的N行中每行是一个自然数A，1≤A≤1000。第i+1行的A表示预先知道的第i+1天的平均汇率，在这一天中，戴维既能用100美元买A马克也能用A马克购买100美元。

【输出】

输出文件的第一行也是唯一的一行应输出要求的钱数(单位为美元，保留两位小数)。 注意：考虑到实数算术运算中进位的误差，结果在正确结果0.05美元范围内的被认为是正确的，戴维必须在最后一天结束之前将他的钱都换成美元。

【样例】 DOLLARS.IN 5 400 300 500 300 250

DOLLARS.OUT 266.66

【样例解释】 (无需输出)

Day 1 ... changing 100.0000 美元= 400.0000 马克 Day 2 ... changing 400.0000 马克= 133.3333 美元 Day 3 ... changing 133.3333 美元= 666.6666 马克 Day 5 ... changing 666.6666 马克= 266.6666 美元

递增序列（incsq）

【问题描述】

给定一个数字串，请你插入若干个逗号，使得该数字串成为一个严格递增的数列且最后一个数要尽可能小，在这个问题中，前导的零是允许出现在数的前面的。

【输入格式】

输入文件中仅有一行，为一个长度不超过80的数字串。

【输出格式】

输出一个严格递增且最后一数最小的数列，相邻两个数之间用一个逗号隔开，如果有多个数列满足要求，则输出第一个数最大的那个数列，若这样的解还不止一个，则输出第二个数最大的那个数列，以此类推。

【输入输出样例】 输入： 100000101

输出： 100,000101

质数取石子(game)

【问题描述】

DD和MM正在玩取石子游戏。他们的游戏规则是这样的：桌上有若干石子，DD先取，轮流取，每次必须取质数个。如果某一时刻某一方无法从桌上的石子中取质数个，比如说剩下0个或1个石子，那么他/她就输了。

DD和MM都很聪明，不管哪方存在一个可以必胜的最优策略，他/她都会按照最优策略保证胜利。于是，DD想知道，对于给定的桌面上的石子数，他究竟能不能取得胜利呢？

当DD确定会取得胜利时，他会说：“不管MM选择怎样的取石子策略，我都能保证至多X步以后就能取得胜利。”那么，最小的满足要求的X是多少呢？

注意：不管是DD取一次石子还是MM取一次石子都应该被计算为“一步”。

【输入格式】

输入文件中的第一行有一个整数N，包含N个测试数据。

从第二行开始，每行有一个测试数据，其中仅包含一个整数，表示桌面上的石子数。

【输出格式】

你需要对于每个输入文件中的N个测试数据输出相应的N行。

如果对于该种情形是DD一定取得胜利，那么输出最小的X；否则该行输出-1。

【输入输出样例】 输入： 3 8 9 16

输出： 1 -1 3

样例说明：

当桌上有8个石子时，先取的DD只需要取走7个石子剩下1个就可以在一步之后保证胜利，输出1。

当桌上有9个石子时。若DD取走2个，MM会取走7个，剩下0个，DD输。若DD取走3个，MM会取走5个，剩下1个，DD输。DD取走5个或者7个的情况同理可知。所以当桌上有9个石子时，不管DD怎么取，MM都可以让DD输，输出-1。

当桌上有16个石子时，DD可以保证在3步以内取得胜利。可以证明，为了在3步内取得胜利，DD第一步必须取7个石子。剩下9个石子之后，不管第二步MM怎么取，DD取了第三步以后可以保证胜利，所以输出3。

【数据范围】

输入文件中的数据数：N<=10。

每次桌上初始的石子数都不超过20000。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库动态规划练习题在线全文阅读。