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

Задачи из рубрикатора

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

Условие задачи  
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 \cdot 10^9\).
 
 
Примеры
Входные данные Выходные данные
1 ????(? 2
 

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

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

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

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

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