Ctrl K

Монеты из стопок

Сложная
На столе лежат несколько стопок монет разного достоинства. Стопка stacks[i] описана сверху вниз: stacks[i][0] — верхняя монета. За один ход можно снять верхнюю монету любой стопки и положить её в карман. Сделайте ровно picks ходов так, чтобы в кармане оказалась наибольшая сумма, и верните эту сумму. До монеты в глубине стопки можно добраться, только сняв все монеты над ней.
Пример 1
stacks=[[4, 50, 2], [9, 10]], picks=2 → 54

Две монеты сверху (4 + 9 = 13 или 9 + 10 = 19) проигрывают паре 4 + 50 = 54 из первой стопки: чтобы добраться до 50, сначала снимаем 4.

Пример 2
stacks=[[20], [20], [1, 1, 90]], picks=3 → 92

Выгоднее забрать всю третью стопку: 1 + 1 + 90 = 92, а не две двадцатки и единицу (41).

Пример 3
stacks=[[7, 3]], picks=1 → 7
Ограничения
  • 1 ≤ len(stacks) ≤ 1000
  • 1 ≤ stacks[i][j] ≤ 10⁵
  • Каждая стопка непустая
  • 1 ≤ picks ≤ общее число монет ≤ 2000
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСамый тяжёлый день чтения СложнаяСлияние соседних кучек группами СложнаяРазрезать торт с ягодами СложнаяРейсы парома со склада СложнаяСлияние плиток спереди Сложная
загружаем Python…
Вход
stacks=[[4, 50, 2], [9, 10]], picks=2
Ожидается
54

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 94 теста на сервере, включая скрытые.