Тема:
Информатика
>>
Алгоритмы
>>
Динамическое программирование
>>
Двойное динамическое программирование
Фильтр
Выбрана 1 задача Убрать все задачи
В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути). Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол. Входные данные Во входном файле задано два числа N и M - размеры таблицы (1<=N<=20, 1<=M<=20). Затем идет N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (числа от 0 до 100). Выходные данные В выходной файл запишите минимальную сумму, потратив которую можно попасть в правый нижний угол. Пример входного файла 3 4 1 1 1 1 5 2 2 100 9 4 2 1 Пример выходного файла 8
Решение
Задачи
Задача 64175 |
|
|
В прямоугольной таблице NxM в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть способов у игрока попасть в правую нижнюю клетку. Входные данные Во входном файле задано два числа N и M - размеры таблицы (1<=N<=10, 1<=M<=10). Выходные данные В выходной файл запишите искомое число способов. Примечание При указанных ограничениях, число способов входит в тип Longint. Пример входного файла 2 3 Пример выходного файла 3 Пояснение Если у нас есть таблица из 2 строк и 3 столбцов, то существуют следующие способы попасть из левого верхнего угла в правый нижний: 1) вниз, вправо, вправо 2) вправо, вниз, вправо 3) вправо, вправо, вниз Еще один пример входного файла 3 3 Пример выходного файла 6
|
|
Решение |
Задача 64176 |
|
|
В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути). Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол. Входные данные Во входном файле задано два числа N и M - размеры таблицы (1<=N<=20, 1<=M<=20). Затем идет N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (числа от 0 до 100). Выходные данные В выходной файл запишите минимальную сумму, потратив которую можно попасть в правый нижний угол. Пример входного файла 3 4 1 1 1 1 5 2 2 100 9 4 2 1 Пример выходного файла 8
|
|
|
Решение |
Задача 98677[Казино] |
|
|
|
Имя входного файла: |
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 |
|
|
|
Решение |
Страница: 1 [Всего задач: 3]
