e-olymp 1442. Одномерная Кликомания

Задача

«Одномерная Кликомания» — это логическая компьютерная игра. Для нее используется полоска размеров $1 \times N$, разбитая на $N$ квадратов $1 \times 1.$ Каждый из квадратов окрашен в красный или желтый цвет.
За один ход игрок может выбрать любой из квадратов и щелкнуть по нему мышкой. В результате компьютер выделяет на полоске группу максимальной длины, состоящую из стоящих подряд квадратов одинакового цвета и содержащую выделенный квадрат, и удаляет все квадраты из этой группы. При этом все квадраты, находящиеся правее удаленной группы (если они существуют), сдвигаются влево так, чтобы пристыковаться к квадратам, находящимся левее удаленной группы (если они существуют) и сохранить целостность полоски:
prb1442-r

Игрок может удалять группы квадратов любой длины, в том числе, состоящие из одного квадрата. Игра продолжается до тех пор, пока все квадраты не удалены.
В начале игры количество баллов у игрока равно нулю. После каждого его хода количество баллов пересчитывается. Если игрок очередным ходом удалил группу из $L$ квадратов, то вычисляется число  $X = A \cdot L + B$, где $A$ и $B$ — некоторые целочисленные константы. Если число $X$ неотрицательное, то количество баллов игрока увеличивается на $X$, иначе оно уменьшается на $-X$.
Цель игрока — набрать по окочанию игры как можно больше баллов. Напишите программу, оптимально играющую в «Одномерную Кликоманию». Программа должна получать на входе цвета всех квадратов исходной полоски, а также целые числа $A$ и $B$, и возвращать максимальное количество баллов, которое может набрать игрок по окончанию игры.

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

В первой строке задана строка, состоящая из символов $’R’/’Y’$, перечисляющих слева направо цвета всех квадратов исходной полоски. Символ $’R’$ соответствует квадрату красного цвета, а символ $’Y’$ — квадрату желтого цвета.
Во второй и третьей строках соответственно целые числа $A(1 \leq A \leq 1000)$ и $B(-100 \leq B \leq 100)$, задающие константы в формуле начисления очков за каждый сделанный ход.

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

Целое число, равное максимальному количеству очков, которое может набрать игрок по окончанию игры.

Тесты

Входные данные Выходные данные
1 YYYYYYY
73
14
525
2 RYRYRYR
100
-100
300
3 YYYRRR
1
-100
-194
4 YRYYRRRYYYYY
12
34
314

Код программы

Решение

По условию задачи необходимо определить максимальное количество очков которое можно получить в игре. Число $a$ всегда положительное и умножается на количество квадратов удалённых за один ход. В конце игры будут удалены все квадраты, а значит этот вклад в общий счёт игры равен $a \cdot n$, где $n$ — количество квадратиков в игре. Число $b$ может быть как положительным так и отрицательным. В первом случае, нам выгодно, что бы игрок совершил максимальное число ходов, то есть ровно столько, сколько содержится последовательностей из квадратиков одного цвета. Если $b$ меньше нуля, то счёт будет наибольший, если игрок сделает наименьшее количество ходов, а именно избавиться от чередования цветов и за один ход удалит все квадраты, это количество последовательностей пополам, плюс один.
Считаем необходимые данные и выводим ответ в зависимости от положительности $b$.

Ссылки

4 thoughts on “e-olymp 1442. Одномерная Кликомания

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