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

Рассмотрим дорогу, подходящую к перекрестку, на котором сходится \(m\) дорог. Водитель, подъезжающий к перекрестку по этой дороге, потенциально может продолжить свое движение в \(m\) различных направлениях — обратно по дороге, по которой он приехал, а также по одной из оставшихся \(m - 1\) дорог. Пронумеруем возможные направления числами от 1 до \(m\) слева направо с точки зрения подъезжающего водителя, номер 1 получит разворот и возврат по дороге, по которой водитель подъезжал к перекрестку, номер 2 — поворот на самую левую из дорог, и т. д.

Пусть дорога содержит \(n\) полос для движения. Пронумеруем полосы от 1 до \(n\) слева направо, самая левая полоса получит номер 1, следующая номер 2, и т. д. Знак <<движение по полосам>> разрешает каждой из полос движение по некоторым из \(m\) возможных направлений. При этом должны выполняться следующие условия:

1. если с \(i\)-й полосы разрешено движение в \(a\)-м направлении, а с \(j\)-й полосы — в \(b\)-м направлении, причем \(i < j\), то \(a \le b\);

2. с каждой полосы разрешено движение хотя бы в одном направлении;

3. в каждом направлении разрешено движение хотя бы с одной полосы.

Инспекция по безопасности дорожного движения заинтересовалась, а сколько различных знаков <<движение по полосам>> можно установить перед таким перекрестком. Помогите им найти ответ на этот вопрос.

Формат входных данных
Строка содержит два целых числа: \(m\) и \(n\) (\(2 \le m \le 50\), \(1 \le n \le 15\)).

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

В примере возможны следующие варианты знаков <<движение по полосам>>:

Алиса и Громозека играют в фишки-палочки. У каждого из них есть набор фишек, на каждой фишке записано одно целое число. Каждый из них  выкладывает свои фишки вдоль двух параллельных горизонтальных линий. Следующим шагом Алиса соединяет палочкой две фишки, расположенные на разных горизонтальных линиях, то есть соединяет одну свою фишку с одной из фишек Громозеки по следующим правилам:

1. числа, на фишке Алисы и на фишке Громозеки равны;
2. соединяющая палочка не должна пересекать другие палочки;
3. две палочки не могут указывать на одну и ту же фишку.

Далее, Громозека считает сколько палочек выложила Алиса. После этого, Алиса убирает свои палочки и фишки соединяет Громозека по тем же правилам. Выигрывает тот, кто выложит по данным правилам больше всего палочек. 

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


Входные данные
Первая строка входных данных содержит число n - количество фишек Алисы. Вторая строка содержит n чисел nums1i - числа на фишках Алисы, в том порядке, в котором она их выложила. Третья строка содержит число m - количество фишек Громозеки. Четвертая строка содержит m чисел nums2j - числа на фишках Громозека, в том порядке, в котором он их выложил. 

Ограничения

• 1 <= n, m <= 500
• 1 <= nums1[i], nums2[j] <= 2000

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

Примечание
Рисунок к первому тестовому примеру

Юный волшебник Айвен отправляется в волшебный лес, чтобы набрать  волшебных кристаллов. Каждый кристалл, растущий в данном лесу, обладает своей массой. Айвен имеет рюкзак, который может выдержать определенный вес M. Айвен хочет использовать свой рюкзак по максимуму и набрать  кристаллов такое количество, чтобы суммарно их вес равнялся в точности весу, который может выдержать его рюкзак. 
Вам стали известны массы кристаллов, которые растут в волшебном лесу. Выведите "YES",  если Айвен сможет набрать кристаллов суммарным весом ровно M, иначе выведите "NO".

Примеры

bbbab

4

Примеры

12

3

Вам даны две строки s1 и s2. За один шаг вы можете удалить из любой строки ровно один символ. Определите минимального количество шагов, необходимое для того, чтобы сделать строки s1 и s2 идентичными.

Ограничения

• 1 <= длина s1 и s2 <= 500;
• s1 и s2 состоят из маленьких английских букв.

Примеры

sea
eat

2

В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке.  За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).
 
Требуется найти наибольшую сумму у.е., заплатив которую игрок может попасть в правый нижний угол, а также маршрут, на котором достигается эта сумма.

В первой строке записаны два числа N и M - размеры таблицы (1<=N<=100, 1<=M<=100). Далее записаны N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (каждое число от 0 до 100).

Первая строка выходных данных содержит максимальную возможную сумму, вторая – маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N-1 букву D, означающую передвижение вниз и M-1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.

Примеры

5 5
9 9 9 9 9
3 0 0 0 0
9 9 9 9 9
6 6 6 6 8
9 9 9 9 9

74
D D R R R R D D 

Примеры

Примеры

Примеры

Домовой Кузьма очень любит играть в шашки на доске 8х8. Когда никто не хочет с ним играть, он просто сидит и думает. Например, сейчас он пытается посчитать сколько есть вариантов провести белую шашку в дамки, если она находится одна на доске?
(Белая шашка ходит по диагонали на одну клетку вверх-вправо или вверх-влево. Шашка проходит в дамки, если попадает на верхнюю горизонталь.)

Вводятся два числа от 1 до 8: номер номер столбца (считая слева) и строки (считая снизу), где изначально стоит шашка.

Выведите одно число - количество вариантов.

Примеры

Примеры

Примеры

Примеры

Примеры

Примеры

Примеры