网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
邮票
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | stamps.in | 输出文件 | stamps.out |
usaco/Stamps(译by Felicia Crazy)
描述
已知一个N枚邮票的面值集合(如,{1分,3分})和一个上限K ——表示信封上能够贴K张邮票。计算从1到M的最大连续可贴出的邮资。
例如,假设有1分和3分的邮票;你最多可以贴5张邮票。很容易贴出1到5分的邮资(用1分邮票贴就行了),接下来的邮资也不难:
- 6 = 3 + 3
- 7 = 3 + 3 + 1
- 8 = 3 + 3 + 1 + 1
- 9 = 3 + 3 + 3
- 10 = 3 + 3 + 3 + 1
- 11 = 3 + 3 + 3 + 1 + 1
- 12 = 3 + 3 + 3 + 3
- 13 = 3 + 3 + 3 + 3 + 1。
然而,使用5枚1分或者3分的邮票根本不可能贴出14分的邮资。因此,对于这两种邮票的集合和上限K=5,答案是M=13。
格式
PROGRAM NAME: stamps
INPUT FORMAT:(file stamps.in)
第1行: | 两个整数,K和N。K(1 <= K <= 200)是可用的邮票总数。N(1 <= N <= 50)是邮票面值的数量。 |
第2行..文件末: | N个整数,每行15个,列出所有的N个邮票的面值,面值不超过10000。 |
OUTPUT FORMAT:(file stamps.out)
单独的一行,一个整数,从 1 分开始连续的可用集合中不多于 K 张邮票贴出的邮资数。
SAMPLE INPUT
(file stamps.in)
5 2
1 3
SAMPLE OUTPUT
(file stamps.out)
13