noip第29课作业

1.   钢条切割

【问题描述】

一家公司购买长钢条，将其切割成短钢条出售，切割本身没有成本，长度为i的短钢条的价格为Pi。那给定一段长度为n的钢条和一个价格表Pi,求钢条的切割方案使得收益Rn最大。如一个Pi如下：

长度i	1	2	3	4	5	6	7	8	9	10
价格pi	1	5	8	9	10	17	17	20	24	40

【输入格式】

一个整数n为钢条的长度（0<n<=1000）。

【输出格式】

一个整数为最大的收益。

【样例输入】

5

【样例输出】

13

【样例输入】

7

【样例输出】

18

【样例输入】

9

【样例输出】

25

【样例输入】

10

【样例输出】

30

2、母牛的故事

【问题描述】

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

【输入格式】

输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。

n=0表示输入数据的结束，不做处理。

【输出格式】

对于每个测试实例，输出在第n年的时候母牛的数量。

每个输出占一行。

【样例输入】

2

4

5

0

【样例输出】

2

4

6

选做题

1、免费馅饼

【问题描述】

都说天上不会掉馅饼，但有一天小童正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来小童的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以小童马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在小径上接。由于小童平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标：

为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时小童站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问小童最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼）

【输入格式】

输入数据的第一行为正整数n(0<n<1000)，表示有n个馅饼掉在这条小径上。在接下来的n行中，每行有两个整数x,T(0<T<1000)，表示在第T秒有一个馅饼掉在x点上。同一秒钟在同一点上可能掉下多个馅饼。

【输出格式】

输出一个整数m，表示小童最多可能接到m个馅饼。

【样例输入】

6

5 1

4 1

6 1

7 2

7 2

8 3

【样例输出】

4

2. 买书

【问题描述】

小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。

问小明有多少种买书方案？（每种书可购买多本）

【输入个数】

一个整数n，代表总共钱数。（0<=n<=1000）

【输出格式】

一个整数，代表方案总数。

【样例输入】

20

【样例输出】

2

【样例输入】

15

【样例输出】

0

3、聪明的老鼠

【问题描述】

吉吉是个小老鼠，它非常的聪明，他知道天敌猫咪为了捉拿它设置了一个陷阱，陷阱是这样的：猫咪在一排相邻的位置上放置了不同数量的奶酪，如果同时吃掉了了两个相邻位置的奶酪，就会惊动猫咪。

问在不惊动猫咪的前提下吃最多的奶酪的数量？

【输入格式】

第1行是一个整数T（T<=50）,表示一共有T组数据。

接下来的每组数据包含两行，第一行是一个整数N（1<=N<=100000）,表示一共有N份奶酪。第2行是N个被空格分开的正整数，表示每份奶酪的数量，每份不超过1000。

【输出格式】

对于每组数据，输出一行。该行包括一个整数，表示吉吉可以吃到的奶酪的总数。

【样例输入】

2

3

1 8 2

4

10 7 6 14

【样例输出】

8

24