04. Скука#
| 🎯 Уровень | 🟠 Middle |
| 🔗 Источник | Codeforces 455A — Boredom |
| 📊 Сложность | 1500 |
| 🏷️ Темы | динамическое программирование |
📝 Условие#
Выбирая число x, вы получаете x очков, но все элементы, равные x - 1 и x + 1, удаляются. Сколько максимум очков можно набрать?
📥 Входные данные#
В первой строке число n (1 ≤ n ≤ 10⁵). Во второй — n чисел a_i (1 ≤ a_i ≤ 10⁵).
📤 Выходные данные#
Одно число — максимальное количество очков.
🧪 Тесты#
Тест 1#
Ввод:
2
1 2
Вывод:
2
Тест 2#
Ввод:
3
1 2 3
Вывод:
4
Тест 3#
Ввод:
9
1 2 1 3 2 2 2 2 3
Вывод:
10
Заметка
Оригинальное условие и проверка решения на всех тестах — по ссылке на источник.
💡 Подсказка#
Открыть, если застрял(а) больше чем на 20 минут
Сгруппируйте по значениям: dp[x] = max(dp[x-1], dp[x-2] + x·cnt[x]).