Блог пользователя ImaDra

Помогите решить.
Автор ImaDra, 11 лет назад, По-русски

Задача на сайте http://informatics.mccme.ru/mod/statements/view3.php?id=1480&chapterid=11#1

Задача на динамику, подскажите как решить?

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

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

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

Формат выходных данных

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

Пример

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

6

a 1

b 4

d 2

x 3

f 1

e 3

fxeeabadd

2

aba

ed

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

16

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Wrong.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Это неверное решение. s="abba", разрешено брать или "aa" или "bb". Меня больше интересует не является ли эта задача, задачей с идущего соревнования? Есть решение, но хочу получить ответ на этот вопрос сначала.

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Нет, точнее, я лично слышал ее несколько лет назад.

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
        ← Rev. 10   Проголосовать: нравится 0 Проголосовать: не нравится

        Ну тогда есть примерно вот такое решение:

        // стоимость схлопывания подстроки с L по R
// если нельзя схлопнуть совсем, то -inf
int DP(int L, int R, int id, int pref) {
 //id - номер разрешенной подпоследовательности, которую мы хотим взять последней.
 // pref - количество символов подпоследовательности id, которые мы уже набрали.
   // здесь пробуем взять очередной символ строки id, или изменить место где мы его будем брать.
   for (int i = L; i < R; ++i) if (s[i] == images[id][pref])
       res = max(res, D(L, i) + cost[s[i]] + D(i + 1, R, id, pref + 1));
   if (pref == len[id]) return D(L, R, 0, 0);
   if (pref == 0) res = max(res, D(L, R, id + 1, 0));
   if (id == maxId) return -inf;
   // возможно ещё какие-то действия.
}

        общая сложность решения, если аккуратно реализовать, должна быть порядка N^3 * (K + sumOfLens), где sumOfLens — сумма длин K строк и не превосходит 150 по условию.

        UPD: если вам кажется что много операций, спешу заметить, что N^3 нужно поделить на 6 т.к. L < R и L <= i < R

        → Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

У меня есть решение этой задачи столетней давности на Паскале. Насколько я понимаю, мое решение работает за кривую экспоненту, однако, проходит. http://pastebin.com/nbVDgshq

→ Ответить