Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование: два параметра --> Динамическое программирование по подстрокам
---> 2 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников
    Муниципальный этап(80 задач)
    Окружная олимпиада(18 задач)
    Региональный этап(109 задач)
    Заключительный этап(97 задач)
Страница: 1 Отображать по:
#11
Казино
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Вновь открытое казино предложило оригинальную игру.

В начале игры крупье выставляет в ряд несколько фишек разных цветов. Кроме того, он объявляет, какие последовательности фишек игрок может забирать себе в процессе игры. Далее игрок забирает себе одну из заранее объявленных последовательностей фишек, расположенных подряд. После этого крупье сдвигает оставшиеся фишки, убирая разрыв. Затем игрок снова забирает себе одну из объявленных последовательностей и так далее. Игра продолжается до тех пор, пока игрок может забирать фишки.

Рассмотрим пример. Пусть на столе выставлен ряд фишек 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 символов, и все они непустые.

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

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

Примеры
Входные данные
3
v 3
l 1
u 2
luvu
3
luv
vul
uuu
Выходные данные
6
#111485
Дубы
  

На аллее перед зданием Министерства Обороны в ряд высажены \(n\) дубов. В связи с грядущим приездом главнокомандующего, было принято решение срубить несколько деревьев для придания аллее более милитаристического вида.

Внутренние распорядки министерства позволяют срубать дуб только в двух случаях:

* Если и ближайший дуб слева, и ближайший дуб справа строго ниже, чем данный дуб.

* Если и ближайший дуб слева, и ближайший дуб справа строго выше, чем данный дуб.

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

Министр хочет выработать такой план вырубки, чтобы в итоге осталось несколько дубов, высоты которых образуют неубывающую последовательность, то есть чтобы каждый дуб был не ниже, чем все дубы, стоящие слева от него. При этом, как человек любящий флору, министр хочет, чтобы было срублено минимальное возможное количество деревьев.

Помогите сотрудникам министерства составить оптимальный план вырубки аллеи или выяснить, что срубить дубы соответствующим образом невозможно.

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

Первая строка входного файла содержит целое число \(n\) — количество дубов, растущих на аллее (\(2\le n \le 200\)). Вторая строка содержит \(n\) чисел — высоты дубов, приведенные слева направо. Высоты дубов — положительные целые числа, не превышающие 1000.

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

Если оставить последовательность дубов с неубывающими высотами невозможно, выходной файл должен содержать только одно число \(-1\).

В случае, если искомый план существует, в первую строку выходного файла выведите целое число \(m\) — минимальное количество дубов, которые необходимо срубить. В следующие \(m\) строк выведите оптимальный план вырубки деревьев — номера дубов в том порядке, в котором их следует срубать, по одному номеру на строке.

Дубы нумеруются слева направо натуральными числами от \(1\) до \(n\).

Если планов с наименьшим числом срубаемых дубов несколько, выведите любой из них.

Система оценки

В 50 баллов оценивается решение для случая, когда все высоты дубов попарно различны.

Примеры
Входные данные
5
3 2 4 8 5
Выходные данные
2
2
4
Входные данные
5
4 5 5 5 6
Выходные данные
0
Входные данные
6
1 1 3 3 2 2
Выходные данные
-1
Входные данные
6
400 300 310 300 310 500
Выходные данные
-1
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест