05. Разрезание ленты#
| 🎯 Уровень | 🟠 Middle |
| 🔗 Источник | Codeforces 189A — Cut Ribbon |
| 📊 Сложность | 1300 |
| 🏷️ Темы | динамическое программирование |
📝 Условие#
Ленту длины n нужно разрезать на куски длины только a, b или c, чтобы кусков было как можно больше.
📥 Входные данные#
В одной строке четыре числа n, a, b, c (1 ≤ n, a, b, c ≤ 4000). Гарантируется, что хотя бы одно разрезание существует.
📤 Выходные данные#
Одно число — максимальное количество кусков.
🧪 Тесты#
Тест 1#
Ввод:
5 5 3 2
Вывод:
2
Тест 2#
Ввод:
7 5 5 2
Вывод:
2
Тест 3#
Ввод:
17 3 5 7
Вывод:
5
Заметка
Оригинальное условие и проверка решения на всех тестах — по ссылке на источник.
💡 Подсказка#
Открыть, если застрял(а) больше чем на 20 минут
Рюкзак: dp[i] — макс. кусков для длины i, недостижимые = -∞.