动态规划练习题

4/4动态规划练习题最小乘车费用(bus)

【问题描述】

而任意一辆汽车从不行驶超过10公里。某人想乘车到达n公里远的地方，假设他可以任意次换车，请你帮他找到一种乘车方案，使得总费用最小。

注意：10公里的费用比1公里小的情况是允许的。

【输入文件】

共两行：

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

第二行为某人想要乘车的公里数(不超过20000的整数)。

【输出文件】

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

【样例输入】

122131404958697990101

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

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

线的数目。

【输入样例】

304

7

224

26

103

1512

98

1717

42

00

【输出样例】

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

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

Day1...changing100.0000美元=400.0000马克

Day2...changing400.0000马克=133.3333美元

Day3...changing133.3333美元=666.6666马克

Day5...changing666.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。沁园春·雪

北国风光，千里冰封，万