e-olymp 657. Игра с монетами

Задача взята с сайта e-olymp

Условие

Однокопеечные монетки разложены в стопки (в стопках может быть различное количество монет), а стопки поставлены на столе в ряд слева направо. Двое противников по очереди делают ходы. Ход состоит в том, что один из игроков берет слева несколько стопок подряд, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более $ K$ стопок. Игра заканчивается, когда стопок не остается. Требуется найти максимальное число монет, которое может получить первый участник после окончания игры, если второй игрок тоже старается ходить так, чтобы получить как можно больше монет.

Входные данные

В первой строке находится сначала число стопок $ N,$ за ним идут $ N$ чисел, задающих количество монет в стопках слева направо, а затем число $ K.$ Все числа в строке разделены пробелами.
$ 1 \leqslant N \leqslant 180, 1 \leqslant K \leqslant 80,$ количество монет в стопке — не менее $ 1$ и не более $ 20 000$.

Выходные данные

Вывести одно число — максимальное количество монет, которое заведомо может получить первый игрок.

Тесты

Inputs Outputs
1 3 4 9 1 3 14
2 4 1 2 2 7 3 5
3 5 3 4 8 1 7 2 18
4 12 67 8 6 12 6 90 54 89 145 32 45 65 4 357
5 14 32 53 5 52 9 8 17 5 87 44 51 12 15 56 10 312
6 14 76 112 3 1 98 4 172 33 65 90 2 71 18 32 14 777

Код

Решение

Анализируя задачу, становится понятно, что ее можно решить методами динамического программирования, а именно трехмерная динамика по параметрам: количество уже взятых стопок — l, количество стопок, которые можно взять kи какой игрок сейчас ходит p. Каждый игрок старается ходить оптимально, тогда для первого игрока задача взять максимальное количество монет, а для второго игрока задача оставить наименьшее количество монет оппоненту. Решение исполнено с помощью рекурсии, где терминальный случай-когда в массиве осталось количество стопок, меньшее или равное тому, сколько игрок может взять. Также стоит проверять высчитывалась ли раньше данная позиция, иначе задача не зайдет по времени.

Ссылки

5 thoughts on “e-olymp 657. Игра с монетами

    • Виктор, боюсь я вас неправильно понял, ну либо вы немного невнимателен. Уточните какая из ссылок, ибо из проверенных мною все ведут куда нужно

  1. Ссылки всего две. Я написал, что ссылка на условие не туда. То есть ссылка, где у Вас написано «e-olymp». При нажатии на эту ссылку, я не попадаю на условие задачи, а попадаю на решении задачи, где показывается на какое количество процентов Вы решили задачу.

    • Ссылка на условие задачи у меня есть в начале публикации: «Задача взята с сайта e-olymp», где e-olymp-ссылка на условие. В конце публикации ссылки на код ideone и на решение на e-olymp. Я все же вижу свой просчет-я не подписал, что в конце ссылка именно на решение и, видимо, вызывал у вас путаницу, исправлено.

  2. Вот ссылка, на которую можно перейти после нажатия у Вас на «e-olymp»: «https://www.e-olymp.com/ru/submissions/5488883». А вот ссылка именно условие задачи: «https://www.e-olymp.com/ru/problems/657».

Добавить комментарий