Динамическое программирование: два параметра


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 18786. Треугольник Паскаля
Темы: Динамическое программирование: два параметра   

Треугольник Паскаля строится следующим образом. Первая строка состоит из одного числа, равного единице. Каждая следующая 
содержит на одно число больше, чем предыдущая. Первое и последнее из этих чисел равны 1, а все остальные вычисляются как сумма числа, стоящего в предыдущей строке над ним и числа, стоящего в предыдущей же строке слева от него.
 
Входные данные
Вводится одно целое число N (\(0<=N<=30\)).
 
Выходные данные 
Выведите N строк треугольника Паскаля. Разделяйте числа в строке одним пробелом.
 

Примечание
Все числа в треугольнике Паскаля при указанных ограничениях входят в Longint.
 
 
Примеры
Входные данные Выходные данные
1
8
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
 

ID 23407. Минимальный путь в таблице
Темы: Динамическое программирование: два параметра   

В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке.
За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено).
При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).
 
Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол.
 
Входные данные
В первой строке записаны два числа N и M - размеры таблицы (\(1<=N<=20\), \(1<=M<=20\)). Далее записаны N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (каждое число от 0 до 100).
 
Выходные данные
Выведите минимальную сумму, потратив которую можно попасть в правый нижний угол.
 
 
Примеры
Входные данные Выходные данные
1
3 4
1 1 1 1
5 2 2 100
9 4 2 1
8

ID 23412. Восстановление скобок
Темы: Динамическое программирование: два параметра    Динамическое программирование по подстрокам   

Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.
 
Входные данные
Вводится строка, которая содержит заданный шаблон длиной не более 80 символов.
 
Выходные данные
Выведите искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2·109.
 
 
Примеры
Входные данные Выходные данные
1 ????(? 2
 

ID 33142. Ход конем_1
Темы: Динамическое программирование    Динамическое программирование: два параметра   

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить ТОЛЬКО на две клетки вниз и на одну клетку вправо, либо на две клетки вправо и на одну клетку вниз (смотри рисунок).
 
 
Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.
 
Входные данные
Во входной строке находятся два натуральных числа N и M (\(1 <= N,\ M <= 50\)).  
 
Выходные данные 
Выведите единственное число количество способов добраться конём до правого нижнего угла доски.
 
Примеры
Входные данные Выходные данные
1 4 4 2

ID 33143. Ход конем - 2
Темы: Динамическое программирование    Динамическое программирование: два параметра   

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке:

 
Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.
 
Входные данные 
Во входной строке находятся два натуральных числа N и M (\(1 <= N,\ M <= 15\)).  
 
Выходные данные 
Выведите единственное число количество способов добраться конём до правого нижнего угла доски.
 
Примеры
Входные данные Выходные данные
1 4 4 2
2 7 15 13309

ID 38286. Нужно больше золота
Темы: Динамическое программирование: два параметра   

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

К сожалению, первый же квест в игре поставил Петю в тупик. Выполнив задание, он получил n магических артефактов, которые можно использовать для получения золота. Для каждого артефакта известна его ценность , для i -го артефакта она равна wi . Для получения золота артефакты можно активировать . Каждый артефакт можно активировать только один раз. Петя может активировать артефакты в произвольном порядке.

У героя, которым управляет Петя, есть магическая сила , исходно она равна нулю. Есть два способа активировать артефакт: с помощью магии и с помощью силы. Если активировать артефакт с ценностью w с помощью магии, то магическая сила героя увеличивается на w . Если же активировать артефакт с ценностью w с помощью силы, то герой получает xw золотых монет, где x — магическая сила героя в момент активации артефакта.

Например, если герой Пети получил 4 артефакта с ценностями 1, 1, 2 и 2, то можно получить 9 золотых монет, действуя следующим образом. Сначала надо активировать с помощью магии по одному артефакту с ценностью 1 и 2. После этого магическая сила героя равна 3, теперь можно активировать с помощью силы оставшиеся артефакты и получить 3 и 6 золотых монет, соответственно.

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

Входные данные
Первая строка входных данных содержит единственное число n — количество магических артефактов ( 1 ≤ n ≤ 100 ).

Вторая строка входных данных содержит n чисел w1 , w2 , ..., wn — ценности артефактов ( 1 ≤ wi ≤ 100 ).

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

Примеры
Входные данные Выходные данные
1 4
1 1 2 2
9

ID 38296. Ежедневные награды
Темы: Динамическое программирование: два параметра   

Миша установил на свой телефон новую игру «Мемтест 2к17». В ней предусмотрены ежедневные награды за посещение. Награды бывают n уровней. Тип награды зависит от награды за предыдущий день, а именно:

если игрок в предыдущий день не посещал игру, то за сегодняшнее посещение он получит награду уровня 1;
если игрок в предыдущий день зашёл в игру и получил награду уровня k ( k ≠ n ), то за сегодняшнее посещение он получит награду уровня k + 1 ;
если игрок в предыдущий день зашёл в игру и получил награду уровня n , то за сегодняшнее посещение он получит награду уровня 1.
На Форуме для Крутых Программистов Миша выяснил, что награды каждого из уровней составляют соответственно a 1 , a 2 , ..., a n золотых монет.
Через m дней состоится турнир по «Мемтест 2к17», к которому Миша хочет собрать как можно больше золотых монет. Помогите ему спланировать посещения игры на протяжении m дней, оставшихся до турнира. Найдите наибольшее количество золотых монет, которое он сможет получить за счёт ежедневных наград в этот период. Можно считать, что игра установлена в первый из этих m дней, то есть до этого Миша в неё ни разу не заходил.

Входные данные
Первая строка входных данных содержит натуральные числа n и m ( 1 ≤ n , m ≤ 1000 ) — количества уровней наград и дней до турнира.

Вторая строка входных данных содержит n целых чисел a 1 , a 2 , ..., a n ( 1 ≤ a i ≤ 1000 ), где a i — величина награды i -го уровня в золотых монетах.

Выходные данные
Выведите одно натуральное число — наибольшее количество золотых монет, которое Миша сможет получить до турнира.

Примечание
В первом тесте из примера Мише выгодно заходить в игру каждый день. Тогда он получит 1 + 2 + 4 = 7 золотых монет.

Во втором тесте из примера Мише выгодно заходить в игру в первый и третий день, получив в каждый из них по 4 монеты, тогда в сумме он получит 8 монет.
 

Примеры
Входные данные Выходные данные
1 3 3
1 2 4
7
2 3 3
4 2 1
8

ID 38515. Бургеры в McDuck's
Темы: Динамическое программирование    Динамическое программирование: два параметра   

Популярная сеть быстрого питания «McDuck's» открыла новый филиал в Берляндии. В ресторане установлено k плит. Для того чтобы приготовить бургер, надо жарить котлету в течение минуты на одной из плит, поэтому ресторан может готовить не более k бургеров в минуту.

Известно, что в «McDuck's» придут n клиентов. i-й из них придёт в момент времени ti, закажет xi бургеров и будет готов заплатить за них ci бурлей. Каждый клиент готов ждать заказ в течение w минут и, если через w минут после прихода он не получил xi бургеров, он не заплатит ничего. При этом каждый клиент готов получать только свежие бургеры, то есть только те, котлеты для которых были поджарены не раньше времени ti. Из-за таких сложных требований ресторан не всегда сможет выполнить все заказы всех клиентов.

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

Входные данные
В первой строке содержатся три целых числа n, k и w (1 ≤ n ≤ 100000, 1 ≤ k ≤ 10, 1 ≤ w ≤ 60) — число клиентов, число плит и время ожидания клиента, соответственно.

Следующие n строк содержат описания клиентов, состоящие из трёх целых чисел — ti, xi, ci (1 ≤ ti, xi, ci ≤ 109) — время (в минутах) прихода i-го клиента, число бургеров, которые он закажет и число бурлей, которые он готов заплатить, соответственно. Клиенты перечислены в порядке возрастания времени прихода, то есть для любого i > 1 верно, что ti−1 ≤ ti.

Выходные данные
В единственной строке выведите одно число — максимальную прибыль ресторана.

Примечание
В первом тестовом примере первую котлету можно поставить жариться в момент времени 0 и тогда в момент времени 1 она будет готова и её можно будет дать в бургере первому клиенту. В момент времени 1 можно поставить жариться ещё одну котлету, она будет готова в момент времени 2 и её можно будет дать в бургере второму клиенту.
 

Примеры
Входные данные Выходные данные
1 2 1 1
1 1 5
1 1 7
12
2 3 2 2
1 6 8
2 5 10
3 4 4
12

ID 40064. Последовательности длины N
Темы: Динамическое программирование: два параметра   

Сколько целых последовательностей длины N, A = (A1,…,AN), удовлетворяют всем приведенным ниже условиям?
1) 1 <= Ai <= M (1 <= i <= N)
2)\(\sum\limits_{i=1}^NA_i \le K\)

Входные данные
На вход подается строка, содержащая три целых числа N, M (1 <= N, M <= 50), K (N <= K <= NM).

Выходные данные
Выведите на ответ на задачу.
 

Примеры
Входные данные Выходные данные Пояснения
1
2 3 4
6
(1,1) (1,2) (1,3) (2,1) (2,2) (3,1)

ID 21845. Удаление
Темы: Динамическое программирование: два параметра   

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

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

После удаления из последовательности трех элементов все остальные сдвигаются на нужные места. Например, из последовательности {1, 2, 3, 4, 5} можно получить последовательность {2, 4}.

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

В первой строке записано целое число n (4 ≤ n ≤ 106) — количество элементов в исходной последовательности. Во второй строке записаны n разделенных пробелами целых чисел — члены последовательности, разделенные пробелами. Все числа в последовательности по модулю не превышают 109.

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

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

Примеры тестов

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

4
1 2 3 4
Выходные данные
1
Входные данные
5
1 2 3 4 5
Выходные данные
-4

Примечание

Тесты разделены на группы, но оцениваются отдельно

  • n ≤ 81 — 20 баллов
  • n ≤ 300 — 10 баллов
  • n ≤ 5000 — 20 баллов
  • Без дополнительных ограничений — 50 баллов 

ID 23364. Билеты в театр
Темы: Динамическое программирование    Динамическое программирование: два параметра   

Не так давно в городе будущего Иннополис достроили первый театр. После тяжелой рабочей недели студенты университета решили сходить в театр. Утром они приехали к открытию кассы театра, чтобы успеть купить билеты. Билет в театр стоит 100 рублей.

Оказалось, что у каждой девочки есть ровно одна банкнота номиналом 100 рублей, а у каждого мальчика — номиналом 1000 рублей. До ребят еще никто не успел купить билет, поэтому касса пуста. Это значит, что кассир выдает сдачу только теми банкнотами, которые получил от других ребят, стоявших раньше в очереди. Кассир обслуживает всех по очереди и не начинает обслуживать следующего человека, если еще не продал билет или не выдал требуемую сдачу предыдущему.

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

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

Формат входных данных
В первой строке задано два целых неотрицательных числа n и m, где n — количество девочек, m — количество мальчиков (1<= n + m < 104).

Формат выходных данных
Выведите остаток от деления числа способов расставить студентов в очередь, чтобы все смогли купить билет, на 109 + 7.
 

Ввод Вывод
18 2 10
8 1 0
12 1 4

ID 27294. Palindromic Paths
Темы: Динамическое программирование    Динамическое программирование: два параметра    Комбинаторика    Строки   

<div>Ферма Джона представлена решёткой <strong>N&times;N</strong> полей (1&le;N&le;500). Каждое поле представлено символом латинского алфавита. Например:</div> <div>ABCD</div> <div>BXZX</div> <div>CDXB</div> <div>WCBA</div> <div>Каждый день корова Беси прогуливается из верхнего левого угла в правый нижний, каждый раз двигаясь на один шаг вправо или вниз. Беси записывает в строку буквы, по которым прошлась. Она огорчится, если у неё получится палиндром (слово, которое читается одинаково слева направо и справа налево), поскольку тогда она запутается, в каком направлении двигалась.</div> <div>&nbsp;</div> <div>Пожалуйста, помогите Беси определить количество различных маршрутов которыми она может получить палиндромы. Различные пути, которыми получаются одинаковые палиндромы учитывать множество раз. Выведите свой ответ по модулю 1,000,000,007.</div> <div>&nbsp;</div> <div><strong>ФОРМАТ ВВОДА</strong>:</div> <div>Первая строка ввода содержит N, и последующие N строк содержат N строк решётки, описывающей поля. Каждая строка содержит N символов в интервале A..Z.<br /> &nbsp; <div><strong>ФОРМАТ ВЫВОДА</strong>:</div> <div>Выведите количество различных путей Беси, формирующих палиндромы по модулю 1,000,000,007.</div> &nbsp; <table border="1" cellpadding="1" cellspacing="1" style="width: 500px"> <tbody> <tr> <td>Ввод</td> <td>Вывод</td> </tr> <tr> <td> <div>4</div> <div>ABCD</div> <div>BXZX</div> <div>CDXB</div> <div>WCBA</div> </td> <td>12</td> </tr> </tbody> </table> </div> Примечание: <div>Беси может сделать следующие палиндромы:</div> <div>&nbsp;</div> <div>1 x &quot;ABCDCBA&quot;</div> <div>1 x &quot;ABCWCBA&quot;</div> <div>6 x &quot;ABXZXBA&quot;</div> <div>4 x &quot;ABXDXBA&quot;</div>

ID 27296. Cow Hopscotch
Темы: Динамическое программирование: один параметр    Динамическое программирование: два параметра    Динамическое программирование    Комбинаторика   

Фермер Джон придумал игру для своих коров
 
Она играется на решётке R*C (2 <= R <= 750, 2 <= C <= 750), где каждый квадрат помечен целым числом от 1 до K (1 <= K <= R*C). Коровы выполняют последовательность прыжков, начиная в левом верхнем квадрате и заканчивая в правом нижнем квадрате и прыжок является корректным если и только если:
 
1) Вы прыгаете на квадрат c другим числом
 
2) Квадрат, куда Вы прыгаете, как минимум на одну строку ниже квадрата, в котором Вы сейчас стоите
 
3) Квадрат, в который Вы прыгаете как минимум на одну колонку правее квадрата, в котором Вы сейчас стоите
 
Пожалуйста, помогите коровам вычислить количество возможных различных последовательностей корректных прыжков из левого верхнего квадрата в правый нижний.
 
INPUT FORMAT:
Первая строка ввода содержит целые числа R, C, K. Каждая из следующих R строк содержит C целых чисел, каждое в интервале 1..K.
 
OUTPUT FORMAT
Выведите количество различных способов пропрыгать из левого верхнего угла в правый нижний, по модулю 1000000007.
 
Ввод Вывод
4 4 4
1 1 1 1
1 3 2 1
1 2 4 1
1 1 1 1
5

ID 29547. Circular Barn
Темы: Динамическое программирование    Динамическое программирование: два параметра    Задача на реализацию    Рекурсия   

У Фермера Джона круглый амбар. Амбар состоит из кольца из n комнат, пронумерованных 1…n по периметру (3≤n≤1,000). Каждая комната имеет двери в две соседние комнаты и одну дверь во внешний мир.
ФД хочет разместить ровно ri коров в комнате i (1≤ri≤1,000,000). Он планирует открыть k внешних дверей (1≤k≤7), через которые коровы будут входить в амбар. Каждая корова затем идёт по часовой стрелке, пока не добредёт до нужной комнаты. ФД хочет открыть двери так, чтобы все коровы вместе прошли как можно меньшее расстояние. Коровы предварительно могут собраться как им выгоднее перед этими незакрытыми дверями (эти перемещения не входят в общее расстояние, учитываемое в задаче). Определите минимальное суммарное расстояние, которое придётся пройти коровам, если ФД наилучшим образом выберет какие k открыть.
 
ФОРМАТ ВВОДА:
Первая строка ввода содержит n и k. Последующие n строк содержат r1…rn.

ФОРМАТ ВВОДА:
Выведите минимальное суммарное расстояние пройденное коровами.
 
Ввод Вывод
6 2
2
5
4
2
6
2
14


ФД может открыть двери 2 и 5. 11 коров войдут в двери 2 и пройдут суммарное расстояние 8 чтобы попасть в комнаты 2,3,4. 10 коров войдут в дверь 5 и пройдут общее расстояние 6, чтобы попасть в комнаты 5,6,1.