|
Название задачи: Казино. |
 |
Условие
|
Имя входного файла: |
casino.in |
|
Имя выходного файла: |
casino.out |
|
Максимальное время работы на одном тесте: |
2 секунды |
|
Максимальный объем используемой памяти: |
64 мегабайта |
|
Максимальная оценка за задачу: |
100 баллов |
Вновь открытое казино предложило оригинальную игру.
В начале игры крупье выставляет в ряд несколько фишек разных цветов. Кроме того, он объявляет, какие последовательности фишек игрок может забирать себе в процессе игры. Далее игрок забирает себе одну из заранее объявленных последовательностей фишек, расположенных подряд. После этого крупье сдвигает оставшиеся фишки, убирая разрыв. Затем игрок снова забирает себе одну из объявленных последовательностей и так далее. Игра продолжается до тех пор, пока игрок может забирать фишки.
Рассмотрим пример. Пусть на столе выставлен ряд фишек rrrgggbbb, и крупье объявил последовательности rg и gb. Игрок, например, может забрать фишки rg, лежащие на третьем и четвёртом местах слева. После этого крупье сдвинет фишки, и на столе получится ряд rrggbbb. Ещё дважды забрав фишки rg, игрок добьётся того, что на столе останутся фишки bbb и игра закончится, так как игроку больше нечего забрать со стола. Игрок мог бы действовать и по-другому - на втором и третьем ходах забрать не последовательности rg, а последовательности gb. Тогда на столе остались бы фишки rrb. Аналогично, игрок мог бы добиться того, чтобы в конце остались ряды rrr или rbb.
После окончания игры полученные фишки игрок меняет на деньги. Цена фишки зависит от её цвета.
Требуется написать программу, определяющую максимальную сумму, которую сможет получить игрок.
Формат входных данных
В первой строке входного файла записано число K (1 ≤ K ≤ 26) - количество цветов фишек. Каждая из следующих K строк начинается со строчной латинской буквы, обозначающей цвет. Далее в той же строке через пробел следует целое число Xi (1 ≤ Xi ≤ 150, i = 1..K) - цена фишки соответствующего цвета.
В (K+2)-ой строке описан ряд фишек, лежащих на столе в начале игры. Ряд задается L строчными латинскими буквами (1 ≤ L ≤ 150), которые обозначают цвета фишек ряда.
В следующей строке содержится число N (1 ≤ N ≤ 150) - количество последовательностей, которые были объявлены крупье. В следующих N строках записаны эти последовательности. Гарантируется, что сумма длин этих N строк не превосходит 150 символов, и все они непустые.
Формат выходных данных
В выходной файл выведите единственное целое число - максимальную сумму денег, которую может получить игрок.
Пример
|
casino.in |
casino.out |
|
6 a 1 b 4 d 2 x 3 f 1 e 3 fxeeabadd 2 aba ed |
16 |
Также доступны документы в формате DOC
Решение
Тесты и проверяющая программа
Решения, написанные членами научного комитета и жюри Всероссийской олимпиады
Разбор задачи "Казино"
Заметим, во-первых, что не любая стратегия игрока приводит к нужному результату. Например, если в примере, разбиравшемся в условии задачи (rrrgggbbb и т.д.), стоимость буквы b будет больше стоимости буквы r, то только один из путей приводит к оптимальному результату: три раза забрать буквы gb. После некоторого размышления можно понять, что всевозможные т.н. "жадные" решения - делать самый выгодный ход, делать самый длинный ход, делать самый левый ход, и т.п. - также в большинстве случаев неверны. Перебирать же все варианты, для каждого из них - опять все варианты, и так далее - оказывается слишком медленным подходом.
Для решения этой задачи применим динамическое программирование. В первой половине решения мы для каждого куска начальной последовательности фишек определим, можем ли мы забрать его целиком, не затрагивая при этом остальные фишки. Иными словами, для всех l и r найдем величину a[l,r], равную 1, если фишки с номерами (то есть позициями в начальном расположении, считая слева) с l по r игрок может за несколько действий все забрать себе, и 0 - в противном случае. Затем по этим данным во второй половине решения мы восстановим ответ к задаче.
Во избежание путаницы будем называть последовательности, объявленные крупье (в отличие от начальной последовательности) словами.
Вторая половина решения проще первой, поэтому начнём с неё. Пусть нам известны величины a[l,r]. Пусть тогда b[l,r] - это максимальная сумма денег, которую можно получить, играя только на отрезке с l-ой фишки по r-ую (то есть, не трогая остальных фишек). Ясно, что если a[l,r]=1, то b[l,r] - это просто сумма стоимостей всех фишек с l-ой по r-ую. Если же a[l,r]=0, то уже не удастся забрать все фишки, соответственно, какая-то из фишек должна остаться - пусть это фишка с номером k. Тогда заметим, что задача распадается на две - для фишек слева от k-ой и для фишек справа от неё, т.е. что b[l,r]=b[l,k-1]+b[k+1,r] (здесь и далее мы считаем, что для любого m b[m,m-1]=0). Но так как номер оставшейся фишки не фиксирован, то в действительности b[l,r] равно максимуму этих величин по всем k:
(*)
(напомним, что эта формула верна при a[l,r]=0). Теперь мы видим, что для нахождения величин b[l,r] можно применить динамическое программирование: если мы будем перебирать r от 1 до длины начальной последовательности, а затем l от r до 1, то к моменту вычисления величины b[l,r] все величины, которые необходимы для её нахождения по формуле (*), уже вычислены. Таким образом, зная величины a[l,r] мы можем найти b[l,r]. Легко видеть, что на этом шаге требуется порядка L3 действий (напомним, что L - это длина начальной последовательности).
Теперь вернёмся к первой половине решения, а именно - нахождению величин a[l,r]. Как узнать, можно ли забрать себе данную последовательность (в нашем случае - кусок начальной) целиком? Во-первых, возможно, эту последовательность можно разделить на две части, каждую из которых можно забрать себе целиком. То есть, если найдётся k такое, что a[l,k]=1 и a[k+1,r]=1, то и a[l,r]=1. Если же так сделать не удаётся, то можно заметить, что если мы всё-таки заберём всю последовательность целиком, то её первую и последнюю фишки мы заберём только на последнем шаге. Пусть на последнем шаге мы заберём некоторое слово S. Тогда задача сводится к тому, чтобы выкинуть из последовательности некоторые куски (можно считать, что для этих кусков величина a уже посчитана, поэтому мы знаем, какие из них можно выкинуть, а какие - нет), оставив первую и последнюю фишки на месте, так, чтобы осталось слово S.
Для решения этой задачи опять применим динамическое программирование. А именно, пусть c[l,r,p,q]=1, если можно из отрезка с l-ой фишки по r-ю можно так выкинуть несколько кусков, чтобы остались первые q фишек слова номер p, и при этом l-я и r-я фишки остались на месте, и 0 - иначе (тогда нас интересует величина c[l,r,p, length(p)], где length(p) - длина слова номер p). Во-первых, ясно, что если первая фишка слова номер p не совпадает с l-ой фишкой начальной последовательности, или q-я - с r-ой, то c[l,r,p,q]=0. В противном случае, пусть (q-1)-я фишка слова получится из k-ой фишки последовательности. Тогда, во-первых, должно быть c[l,k,p,q-1]=1 (чтобы получить первые q-1 фишек), а, во-вторых, a[k+1,r-1]=1 (чтобы выкинуть кусок между (q-1)-й фишкой и q-й). Но так как число k не фиксировано, то получаем, что c[l,r,p,q]=1 тогда и только тогда, когда найдётся такое k. Тем самым получен алгоритм для подсчета c. Оценим время его работы. На подсчёт одного элемента массива c требуется порядка L действий (по количеству возможных k). Нам необходимо подсчитать элементы вида c[l,r,p,length(p)]. Из вышеприведённых рассуждений легко заметить, что для их подсчёта нам потребуется подсчёт только элементов вида c[l,...,...,...], а элементов такого вида порядка L∙S (где S - сумма длин всех слов), так как для параметра r есть порядка L вариантов, а для пары параметров (p,q) - порядка S вариантов. Тем самым мы для любых l и r можем найти a[l,r] за порядка L∙L∙S= L2∙S действий, а общее время работы получается порядка L2∙L2∙S=L4∙S.
Однако легко заметить, что если подсчитать все величины c[l,r,p,q] сначала, а потом лишь использовать найденные значения, то время работы будет меньше. Действительно, всего в массиве c L2∙S элементов, и на подсчёт каждого из них уйдёт порядка L действий, тем самым общее время работы будет порядка L3∙S.
Также доступны документы в формате DOC
