Ссылка на задачу — 2140. Solving Questions With Brainpower.
📋 Описание задачи
- Дан вектор
questions (questions[i] = [pointsi, brainpoweri]).
- Вы проходите тест, состоящий из последовательности вопросов.
- Если вы решаете вопрос
i, то зарабатываете pointsi баллов, но пропускаете следующие brainpoweri вопросов.
- Вопросы можно пропускать
- Нужно определить, максимальное количество баллов, которое можно набрать, действуя оптимально.
📌 Пример:
- Вход:
questions = [[3, 2], [4, 3], [4, 4], [2, 5]]
- Размышления:
- Если решить вопрос
0, вы получите 3 очка и пропустите вопросы 1 и 2, перейдёте сразу к 3 → итого: 3 + 2 = 5.
- Если пропустить
0 и решить 1, вы получите 4 очка и пропустите 2 и 3 → итого: 4.
- Если пропустить
0 и 1, решить 2 → получите 4 очка, но пропустите 3 → итого: 4.
- Если пропустить
0–2 и решить 3 → получите 2 очка.
🔎 Оптимальная стратегия: решить вопросы 0 и 3, что даст нам 5 баллов на экзамене.
- 👉 Ответ:
5.
💡 Идея
Читать дальше →