#6959. A. 切割绸带(Cut Ribbon)
A. 切割绸带(Cut Ribbon)
A. 切割绸带(Cut Ribbon)
**时间限制:**1 秒
**内存限制:**256 MB
题目描述
Polycarpus 有一条长度为 (n) 的绸带。他想把绸带切成若干段,并满足以下条件:
- 每段的长度必须是 (a)、(b)、(c) 中的一个。
- 在满足上述条件的前提下,切出的段数尽可能多。
请帮助 Polycarpus 求出最多能切出多少段。
输入格式
一行包含四个整数 (n,a,b,c),分别表示原绸带的长度,以及切割后每段允许的三种长度。
这三个允许长度可能相同。
输出格式
输出一个整数,表示最多能切出的段数。
保证至少存在一种符合条件的切割方案。
数据范围
样例 1
输入
5 5 3 2
输出
2
说明
可以切成长度分别为 (2) 和 (3) 的两段。
样例 2
输入
7 5 5 2
输出
2
说明
可以切成长度分别为 (5) 和 (2) 的两段。
| 测试点编号 | 层级 | n |
a, b, c |
特殊性质 | 标准输出 | 设计目的 |
|---|---|---|---|---|---|---|
| 1 | 弱数据 | 1 | 1, 1, 1 |
最小规模、三种长度相同 | 1 | 检查初始化和最小可达状态 |
| 2 | 7 | 5, 2, 5 |
长度重复、必须精确拼接 | 2 | 检查重复长度及不能把剩余长度忽略 | |
| 3 | 边界数据 | 4, 5, 6 |
无法恰好拼出 | -1000000000 | 检查不可达状态;这是当前代码的实际输出 | |
| 4 | 正常数据 | 20 | 3, 5, 7 |
多种可行组合 | 6 | 检查在精确拼接的前提下最大化段数 |
| 5 | 极限数据 | 4000 | 17, 23, 31 |
大规模、复杂精确组合 | 232 | 检查完整 DP 范围及较复杂的最优组合 |
相关
在以下作业中: