|
Игра с монетами
(Время: 1 сек. Память: 16 Мб Сложность: 47%)
Введем обозначения: s[r] − суммарное количество монет в стопках с r-той по n-ю; g[r, m] − максимальное количество монет, которое может получить игрок, если сейчас его ход, при условии что остались стопки с r-той по n-ю, и он может взять не более m стопок. Элементы массива s[1..n] будут использоваться для вычисления элементов массива g[n, k], поэтому его нужно вычислить и сохранить сразу после ввода данных.
Далее вычисляем элементы массива g. Если игрок может взять все оставшиеся стопки, то он должен сделать это, иначе другой игрок возьмет не менее одной стопки из оставшихся стопок, и выигрыш игрока , чей сейчас ход, не будет максимальным. Следовательно, все числа g[r, m], где m ≥ n − r + 1, определены, в том числе все элементы g[n, m]. А именно, g[r, m]=s[r].
Будем находить элементы g[r, m] в порядке убывания r, при условии m < n − r + 1 . В этой ситуации игрок может взять от одной до m стопок. Пусть он взял i стопок. Тогда другой игрок окажется в ситуации (r + i, i) − его ход, разыгрываются стопки с (r + i) − той по n − ю, и можно взять не более i стопок. Он может взять максимальное количество монет, равное g[r + i, i]. Так как в стопках с r-той по n-ю было s[r] монет, то первый игрок , взяв i стопок, получит s[r] − g[r+i, i] монет.
Поэтому максимальный выигрыш первого игрока определяется по формуле:
Ответом задачи будет число g[1, k] − столько монет может получить первый игрок, если разыгрываются стопки с 1-й по n-ю и можно взять не более k стопок.
| |
