Ссылка на задачу — 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.
💡 Идея
Читать дальше →
Ссылка на задачу — 873. Length of Longest Fibonacci Subsequence.
📌 Описание задачи
Дан монотонно возрастающий массив arr. Нужно найти длину самой длинной фибоначчиевой подпоследовательности, где каждые три последовательных элемента x, y, z удовлетворяют свойству: z = x + y
Если такой подпоследовательности нет, вернуть 0.
💡 Идея
- Мы используем динамическое программирование для отслеживания самой длинной допустимой фибоначчиевой подпоследовательности для всех нетривиальных пар
(z, y), где:
x,y,z=x+y ∈ arr и x<y<z
- Рекурентное правило ДП:
dp[z,y]=dp[y,x]+1
- Для поиска подходящих
(x, y) к текущему z применяем двунаправленный итератор.
📌 Подробности метода
- Перебираем
z = arr[k], начиная с k = 2, так как нужны минимум 3 числа.
- Будем использовать два указателя (
front и back) на arr[..k]:
front движется вперёд (x увеличивается).back движется назад (y уменьшается).
- Сравниваем
x + y и z:
Читать дальше →
Ссылка на задачу — 2467. Most Profitable Path in a Tree.
📌 Описание задачи
Дано неориентированное корневое дерево с n узлами (нумерованными от 0 до n-1).
- У каждого узла есть врата, открытие которых может принести прибыль или потребовать затрат (
amount[i]).
- Алиса начинает движение от корня (
0) к какому-либо листу, выбирая максимально выгодный путь.
- Боб начинает движение из указанной вершины
bob и движется к корню (0).
- Если Алиса и Боб одновременно посещают узел, они делят
стоимость/прибыль пополам.
Нужно найти максимальный чистый доход Алисы при оптимальном выборе пути.
💭 Идея
Вместо раздельного запуска BFS для поиска пути Боба и последующего прохода динамического программирования по узлам дерева, мы решим задачу одним рекурсивным DFS-проходом.
Для каждого узла будем вычислять:
alice_profit[node] – максимальный доход, который может собрать Алиса из поддерева.bob_distance[node] – расстояние на пути Боба до этой вершины.- Если Боб раньше доберётся до узла → Алиса ничего не получит.
Читать дальше →