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

117 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Черепаха#27086
Черепаха хочет переползти из левого верхнего угла поля размером N на M клеток ( 1 ≤ N , M ≤ 16 ) в правый нижний. За один шаг она может переместиться на соседнюю клетку вправо или на соседнюю клетку вниз. Определите, сколькими различными способами Черепаха может добраться до цели.
 
Входные данные
Входная строка содержит два натуральных числа: размеры поля N и M , разделённые пробелом ( 1 ≤ N , M ≤ 16 ).
 
Выходные данные
Программа должна вывести одно число: количество различных маршрутов из левого верхнего угла поля в правый нижний.
 
 
Примеры
№ Входные данные Выходные данные
1 3 3 6
Динамическое программирование на таблицах
✓ 67✗ 50500лёгкаяВойти и решать
Зоомагазин-2#27084
В зоомагазине нужно расставить в один ряд клетки с кошками и собаками. В ряд помещается N клеток, при этом есть одно ограничение: нельзя ставить подряд три клетки с животными одного вида (иначе они передерутся). Предполагается, что в магазине есть неограниченное количество клеток с кошками и собаками. Определите, сколькими безопасными способами можно расставить N клеток в ряд.
 
Входные данные
Входная строка содержит одно натуральное число – количество клеток в ряду N .
 
Выходные данные
Программа должна вывести количество безопасных способов расстановки N клеток в ряд.
 
Ввод Вывод
5 16


 
Динамическое программированиеДинамическое программирование: два параметра
✓ 49✗ 23700средняяВойти и решать
Упорядочите шарики#27053
При игре в новую игру (некоторый гибрид боулинга и бильярда) используется N шариков, пронумерованных числами от 1 до N. В начале игры эти шарики должны быть выложены в линию в порядке своих номеров. В процессе игры их порядок может меняться.
 
Для того, чтобы упорядочить шарики перед началом следующей партии, используется следующее устройство. Это устройство состоит из головки, которая, перемещаясь над шариками, может «засасывать» и «выплевывать» шарики. Чтобы получить большее представление об этом устройстве, представьте себе пылесос, который может засасывать шарики, перемешаться в нужное место, и там, включаясь на продув в обратном направлении, шарики «выплевывать».
 
При засасывании шарика все шарики, которые находились правее засасываемого, сдвигаются влево. «Выплюнуть» шарик можно между любыми двумя шариками (а также перед первым шариком или после последнего), тогда выплевываемый шарик вставляется между этими шариками, и все шарики, которые находятся правее вставляемого, сдвигаются вправо.
 
В устройство может быть одновременно засосано больше одного шарика, при этом при выплевывании шарика первым выплевывается последний засосанный шарик, затем - предпоследний и т.д. (т.е. устройство работает по принципу стека). Шарики выплевываются по одному, т.е. можно выплюнуть только один шарик, остальные оставив внутри устройства (при этом дальше можно как продолжать «выплевывать» шарики в том же или в другом месте, так и засасывать новые шарики).
 
Наиболее энергоемкой из описанных операций является операция засасывания шарика, поэтому хочется минимизировать количество именно таких операций.
 
Напишите программу, которая по данному начальному расположению шариков определит минимальное количество операций засасывания, которое нужно, чтобы расположить шарики в порядке их номеров.
 
Входные данные
Во входном файле задано сначала число N — количество шариков (1<= N <= 1000). Далее идет N чисел, задающих номера шариков в порядке слева направо в их текущем расположении (каждое число — от 1 до N, и каждое из чисел встречается в последовательности ровно один раз).
 
Выходные данные
В выходной файл выведите одно число — минимальное количество операций засасывания шарика, которое потребуется, чтобы расположить шарики в порядке их номеров.
 

Комментарии к примерам тестов
 
1.Можно засосать, например, шарик номер 2 и выплюнуть его между 1-м и 3-м шариком.
 
2. Можно действовать, например, так. Сначала засосем шарик номер 1, затем – шарик номер 2. Затем переместимся в начало и перед 4-м шариком выплюнем шарик (это будет шарик номер 2). Дальше засосем шарик номер 3, и выплюнем его между шариками 2 и 4. Дальше переместимся в начало и там выплюнем шарик номер 1. Впрочем, это не единственный возможный вариант упорядочения шариков в этом примере.

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

 
Динамическое программированиеДинамическое программирование: последовательности
✓ 70✗ 24500лёгкаяВойти и решать
Возрастающая подпоследовательность#27052
Даны N целых чисел X1, X2, ..., XN. Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.
 
Входные данные
В первой строке находится число N. В следующей строке - N чисел через пробел. 1 <= N <= 10 000, 1 <= Xi <= 60 000.
 
Выходные данные
В первой строке выводится количество невычеркнутых чисел, во второй - сами невычеркнутые числа через пробел в исходном порядке. Если вариантов несколько, вывести любой.
 
 
Примеры
№ Входные данные Выходные данные
1
5
1 3 5 2 4
3
1 3 4
Динамическое программирование: последовательности
✓ 221✗ 1 024700средняяВойти и решать
Максимальная прибыль#24755

Вы работаете менеджером и составляете план работ на следующий месяц. Каждый месяц разделён на T равных единиц времени. Всего имеется n задач, которые необходимо сделать. Однако, вы понимаете, что, возможно, успеть сделать все задачи за месяц не получится и хотите составить оптимальный план, выбрав для выполнения некоторые из них.

Про каждую задачу известно время ti, которое нужно затратить, чтобы сделать её, а также прибыль pi, которую сделанная задача принесёт компании. Вы хотите включить в план некоторые задачи так, чтобы:

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

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

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

В первой строке  находятся натуральные числа T (1 ≤ T ≤ 100 000) и n (1 ≤ n ≤ 10) - число единиц времени в месяце и число задач.

Следующие n строк содержат по два натуральных числа ti и pi (1 <= ti, pi <= 100 000) - время, которое необходимо затратить на выполнение i-й задачи и прибыль, которую можно получить, выполнив её.


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

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

 
Примеры
№ Входные данные Выходные данные
1 10 3
8 100
3 10
3 10		 100
2 10 4
5 10
5 20
2 5
2 6		 31
битмаскиЗадача о рюкзаке
✓ 56✗ 87700средняяВойти и решать
Вупсень и Пупсень 2#24637
Как вы уже знаете, Вупсень очень любит давать задачи на поиск наибольшей общей подпоследовательности, а Пупсень очень любит давать задачи на поиск наибольшей правильной скобочной подпоследовательности. Лунтик решил обрадовать своих друзей и подарить им на новый год две строки. Конечно же, Вупсень и Пупсень сразу, не посмотрев на строки, захотели дать задачу на поиск наибольшей общей правильной скобочной подпоследовательности, но не тут то было: в этих строках не было скобок. Лунтик понимал, что если Вупсень и Пупсень увидят решения с битсетами, то будут грустить, и весь праздник испортится, поэтому он придумал другую задачу: найдите длину наибольшего общего подпалиндрома.

Подпалиндромом называется такая попоследовательность строки, которая читается справа налево также, как и слева направо.
 
Формат входный данных
В первой строке дана строка s, во второй строке строка t, состоящие из строчных латинских букв. 1 <= |s|, |t| <= 50.
 
Формат выходных данных
Выведите одно целое число n - длину наибольшей общей подпоследовательности, являющейся палиндромом.
 
Примеры
Ввод Вывод
mem
kek
 1
acab
abca
 3
(с) Буков Антон, 11и
Динамическое программирование по подстрокам
✓ 1✗ 31 200средняяВойти и решать
Уравнение с пропущенными цифрами#23416
Задано уравнение вида A+B=C, где A, B и C - неотрицательные целые числа, в десятичной записи которых некоторые цифры заменены знаками вопроса (?). Примером такого уравнения является ?2+34=4?. Требуется так подставить вместо знаков вопроса цифры, чтобы это равенство стало верным, либо определить, что это невозможно. Найти только одно из  возможных решений.
 
Входные данные
Вводится строка, представляющая собой заданное уравнение без пробелов. Длина уравнения не превышает 80 символов. 
 
Выходные данные
Требуется вывести верное равенство, полученное из исходного уравнения заменой знаков вопроса цифрами, либо сообщение "No solution".
 

Примеры
№ Входные данные Выходные данные
1 ??2?4+9?=355 00264+91=355
 
Динамическое программированиеДинамическое программирование по подстрокам
✓ 2✗ 371 300средняяВойти и решать
Подпоследовательности#23409
Дана последовательность, требуется найти длину наибольшей возрастающей 
подпоследовательности.
 
Входные данные
В первой строке входного файла записано число N - длина последовательности  (1 <= N <= 1000). Во второй строке записана сама последовательность  (через пробел). Числа последовательности - целые числа,  не превосходящие 10000 по модулю.
 
Выходные данные
В выходной файл требуется вывести наибольшую длину возрастающей подпоследовательности.
 
Примеры
№ Входные данные Выходные данные
1
6
3 29 5 5 28 6
 3
 
 
 
Динамическое программирование: последовательности
✓ 509✗ 950300лёгкаяВойти и решать
Минимальный путь в таблице#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
Динамическое программирование: два параметра
✓ 722✗ 745400лёгкаяВойти и решать
**Столовские котлеты#23380
Главный повар решил устроить в лицее День Уважения к Повару. Для этого он приготовил лицеистам N необычайно вкусных котлет и втайне постановил, что первый пожаловавший отведать поварское кушанье школьник должен получить наибольшее количество вкусных котлет, а каждый последующий - строго меньше, чем предыдущий (повару очень не нравилось, когда к приготовленному им обеду опаздывали и тот вынужден был остывать).
 
Конечно, введенное правило оставляет существенный произвол в числе котлет, получаемых очередным явившимся лицеистом, и это число не в последнюю очередь  будет зависеть от предыдущего поведения лицеиста в столовой, а также от волшебных слов, произносимых им. Например, 6 котлет могут быть в  результате распределены по одной из следующих четырех схем: 3+2+1 (три котлеты первому из пришедших школьников, две - второму и одну - третьему), 4+2, 5+1 и 6 (все котлеты съедает счастливчик, пришедший первым).
 
Напишите программу, определяющую, каким количеством различных способов повар может распределить приготовленное лакомство среди школьников.
 
Входные данные
Входной файл содержит одно целое число N - количество приготовленных поваром котлет (0<=N<=200).
 
Выходные данные
Выходной файл должен содержать одно целое число, равное количеству возможных распределений котлет.

 

Примеры
№ Входные данные Выходные данные
1 6 4
 
Задача о рюкзаке
✓ 415✗ 937800средняяВойти и решать
НВП на отрезке#23377
Нам дана числовая последовательность a1, ..., an . Напишите программу, отвечающую на запросы вида "найти длину наибольшей строго возрастающей подпоследовательности, все элементы которой находятся на отрезке с li-ого по ri-ый элемент".
Подпоследовательностью последовательности a1 , ..., an называется последовательность, которую можно получить путем удаления нескольких элементов ai (относительный порядок оставшихся элементов менять запрещается). Так, например, последовательность (2, 4) является подпоследовательностью последовательности (1, 2, 3, 4, 5) (можно удалить элементы 1, 3  и 5 ),  а последовательность (5, 1) - нет.
 
Входные данные
В первой строке записано целое число n  (1 <= n <= 3000 ) - число элементов в последовательности. Во второй строке записано n  чисел, разделенных пробелами - элементы последовательности. Все элементы не превосходят по модулю 109. В третьей строке записано одно целое число q  (1 <= q <= 105) - количество запросов. В следующих q  строках описаны запросы. Описание i -ого запроса - два числа li и rj (1 <= li <= ri <= n) ,  записанные через пробел.
 
Выходные данные
Выведите q чисел - ответы на запросы. Числа следует выводить по одному на строке в том же порядке, в котором запросы описаны во вводе.
 
Примеры
№ Входные данные Выходные данные
1 6
3 3 -5 7 4 9
6
1 4
1 2
2 3
1 5
3 5
2 5		 2
1
1
2
2
2
Динамическое программирование: последовательности
✓ 39✗ 4321 000средняяВойти и решать
Билеты в театр#23364
Не так давно в городе будущего Иннополис достроили первый театр. После тяжелой рабочей недели студенты университета решили сходить в театр. Утром они приехали к открытию кассы театра, чтобы успеть купить билеты. Билет в театр стоит 100 рублей.

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

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

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

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

Формат выходных данных
Выведите остаток от деления числа способов расставить студентов в очередь, чтобы все смогли купить билет, на 109 + 7.
 
Ввод Вывод
18 2 10
8 1 0
12 1 4
Динамическое программированиеДинамическое программирование: два параметра
✓ 3✗ 651 100средняяВойти и решать
Ведьмак#22027
По приезде Геральда в Каэр-Морхен уже наступила зима. Вокруг стояла тишина, а окна замка приветливо светились в темноте. Редкие факелы создавали теплую и согревающую атмосферу, освещая ровный белый ковер из снега. Среди этой красоты особенно порадовал Геральда отъезд Весемира, ведь теперь можно закатить грандиозную пьянку!
Для этого на кухонный стол достали n кружек. Геральд суетился и переставлял кружки с l по r в позицию i, Ламберт с упоением доливал Ривский эль в кружки с l по r по s литров в каждую, а вот Эскель , пока никто не видит, выпивал или доливал в каждую кружку с l по r столько, чтобы в них осталось ровно по k литров в каждой. Спустя почти час Йеннифер, которой порядком надоела брань Ламберта и Эскеля, спустилась вниз, чтобы узнать причину шума. После небольшой перепалки Йеннифер решила помочь отнести кружки в главную столовую, где бурное веселье ведьмаков не мешало бы ей спать. Но так как кружки очень тяжелые, то она может унести не более l литров. Естественно, она хочет пойти спать как можно быстрее, а значит собирается унести как можно больше эля, но общим весом не более l.

Помогите Йеннифер узнать, какой максимальный вес и количество кружек с таким весом она может унести?

Формат входных данных
Дано число n(1 <= n <= 10^4) количество кружек и q(1 <= q <= 10^4) – количество операция. Далее идет описание операций(1 <= l <= r <= 10^4)
• G l r i - Геральд переставляет кружки с l по r в позицию I (1  <= I <=10^4+1)(вставка отрезка производится перед указанным индексом)
• L l r s - Ламберт доливает в кружки с l по r по s литров (1 <= s <= 10^3)
• E l r k – Эскель выпивает из кружек с l по r так, чтобы в каждой оказалось по k литров (1 <= k <= 10^3)
Затем на новой строке идет число l(1 <= l <= 10^5) – количество литров которые может унести Йеннифер. 
Изначально в кружках по 0 литров.

Формат выходных данных
На первой строке через пробел вывести последовательность кружек после проделанных операций, а на второй строке максимальное количество кружек, которые сможет унести Йеннифер и их общий вес. 
 
Пример входных данных Пример выходных данных
5 7
L 2 5 10
G 1 3 5
L 1 4 3
L 3 3 4
E 2 3 2
E 2 2 4
E 5 5 15
15		 13 4 2 13 15
2 15
 
 
5 6
E 1 1 1
E 2 2 2
E 3 3 3
E 4 4 4
E 5 5 5
G 5 5 1
10		 5 1 2 3 4
4 10
5 8
E 1 1 1
E 2 2 2
E 3 3 3
E 4 4 4
E 5 5 5
G 5 5 1
G 1 1 6
G 1 5 1
10		 1 2 3 4 5
4 10

Пояснения к 1 примеру
1. 0 10 10 10 10
2. 10 0 10 10 10
3. 13 3 13 13 10
4. 13 3 17 13 10
5. 13 2 2 13 10
6. 13 4 2 13 10
7. 13 4 2 13 15
Йеннифер может унести 15 литров. Это значит что она может взять либо одну кружку (15 литров или 13 литров), либо две кружки(4 и 2 литра или 13 и 2 литра). Так как она хочет унести как можно больше кружек, то ответ 2.
Пояснения к 3 примеру
1. 1 0 0 0 0
2. 1 2 0 0 0
3. 1 2 3 0 0
4. 1 2 3 4 0
5. 1 2 3 4 5
6. 5 1 2 3 4
7. 1 2 3 4 5
8. 1 2 3 4 5
Йеннифер может унести 10 литров. Наилучший вариант будет 4 и 3 и 2 и 1 литр. Ответ 4.

(с) Аксенов Владимир 10и
Задача о рюкзакереализация
✓ 1✗ 31 200средняяВойти и решать
Минимальный путь в таблице#22016
В прямоугольной таблице 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
 
Динамическое программирование на таблицах
✓ 119✗ 109700средняяВойти и решать
Число способов#22015
В прямоугольной таблице NxM в начале игрок находится в левой верхней клетке.
За один ход ему разрешается перемещаться в соседнюю клетку 
либо вправо, либо вниз (влево и вверх перемещаться запрещено).
Посчитайте, сколько есть способов у игрока попасть в правую
нижнюю клетку.
 
Входные данные
Во входном файле задано два числа N и M - размеры таблицы (1<=N<=10,
1<=M<=10).
 
Выходные данные
В выходной файл запишите искомое число способов. 
 
Примечание
При указанных ограничениях, число способов входит в тип Longint.
 
Пример входного файла
2 3
 
Пример выходного файла
3
 
Пояснение
Если у нас есть таблица из 2 строк и 3 столбцов, то существуют следующие 
способы попасть из левого верхнего угла в правый нижний:
1) вниз, вправо, вправо
2) вправо, вниз, вправо
3) вправо, вправо, вниз
 
Еще один пример входного файла
3 3
 
Пример выходного файла
6
 
Динамическое программирование на таблицахДинамическое программирование: один параметрКомбинаторика
✓ 21✗ 29800средняяВойти и решать
Удаление#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 баллов 
Динамическое программирование: два параметра
✓ 2✗ 211 200средняяВойти и решать
Треугольник Паскаля#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
 
Динамическое программирование: два параметра
✓ 611✗ 650400лёгкаяВойти и решать
Поделиться
Класснуть