Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование: два параметра --> Динамическое программирование на таблицах
---> 46 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 4 5 6 7 8 9 10 >> Отображать по:
#2965
Максимальная стоимость маршрута
  

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

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

Формат входных данных

В первой строке входных данных записаны два натуральных числа N и M, не превосходящих 100 — размеры таблицы. Далее идет N строк, каждая из которых содержит M чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0 до 100.

Формат выходных данных

Программа должна вывести единственное число: максимальную возможную стоимость маршрута черепашки.
Ввод Вывод 
3 4
1 1 2 1
2 2 1 1
2 1 2 1
 
9

#2966
Вывести маршрут максимальной стоимости
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

В первой строке входных данных записаны два натуральных числа N и 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
#3343
Кирпичи (BCD)
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Имеется бесконечное количество прямоугольных кирпичей размерами \(x_i \times y_i \times z_i\), каждый из которых можно ставить на любую грань (размеры каких-то двух стороны будут размерами основания, размер третьей стороны – высотой). Ваша задача – написать программу, находящую максимальную высоту башни, которую можно построить из этих кирпичей. Один кирпич может быть поставлен на другой, если размеры основания верхнего кирпича строго меньше соответствующих размеров основания нижнего.

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

В первой и единственной строке входного файла записано целое число \(N\) (\(1 \leq N \leq 30\)) – количество типов кирпичей, за которым следуют \(3\times N\) целых чисел (\(N\) троек \(x_i\), \(y_i\), \(z_i\)) описывающих размеры каждого типа кирпичей (\(1 \leq x_i, y_i, z_i \leq 65000\)).

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

Выведите в выходной файл единственное целое число - максимальную высоту башни.

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

Входные данные
1 10 20 30
Выходные данные
40
Входные данные
2 6 8 10 5 5 5
Выходные данные
21

#3365
Дорожное движение
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

В городе Z в час пик очень оживленное движение. Неправильно выбранный маршрут может на долгое время задержать вас в пути. Вам известно, что схема города представляет собой N горизонтальных и M вертикальных односторонних дорог, образующих прямоугольник N-1 на M-1 километр. На пересечении каждой вертикальной и горизонтальной дороги находится перекресток, на котором можно изменить направление движения. Заметьте, что для изменения направления движения нужно сначала полностью затормозить.
Вы находитесь в точке (1, 1), или другими словами, в левом нижнем углу города. Движение происходит слева направо и снизу вверх. Вам необходимо добраться до точки (N, M) за наименьшее время. Проблема в том, что на каждой дороге свой скоростной режим и максимальное ускорение, которое можно развить, разное для каждой дороги (и равно, соответственно, \(A_i\) км/\(c^2\) для вертикальной дороги с номером i и \(B_j\) км/c2 для горизонтальной дороги с номером j). При этом скорость на дорогах не ограничена. Ускорение и торможение происходит по стандартным физическим законам.
Однако ваше преимущество состоит в том, что вы хорошо знаете город и можете попасть напрямую с перекрестка (i, j) на перекресток (i+1, j+1), в объезд главных дорог (перед этим также нужно полностью затормозить). Время, необходимое для этого, не зависит от номера перекрестка и равно C. Дороги пронумерованы в порядке, соответствующем направлению движения. Напомним, что движение на всех дорогах одностороннее.

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

В первой строке входного файла расположены числа \(N\), \(M\) и \(C\) (\(1 \leq N, M \leq 1000\), \(10^{-3} \leq C \leq 10\)). Далее, во второй и третьей строках расположены числа \(A_1\), ..., \(A_N\) и \(B_1\), ..., \(B_M\), соответственно (\(10^{-3} \leq A_i, B_i \leq 10\)).

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

В первой строке выходного файла выведите искомое время с восемью знаками после запятой. Во второй строке укажите количество перекрестков \(K\), через которые проходит маршрут, включая первый и последний. Далее, в \(K\) строчках выведите координаты соответствующих перекрестков. Выведите координаты только тех перекрестков, где нужно затормозить(учтите, что после каждого переезда по диагонали нужно затормозить).

Примеры
Входные данные
2 2 4.0
2.0 2.0
2.0 2.0
Выходные данные
2.82842712
3
1 1
1 2
2 2
#3372
Жадная волна
  
ограничение по времени на тест
0.2 second;
ограничение по памяти на тест
64 megabytes

Поле размером \(N\times M\) клеток заполнено целыми числами. Требуется найти на поле клетку, из которой волна, запущенная не более чем на \(K\) итераций, покроет площадь с максимальной суммой расположенных на ней чисел.
Пример распространения волны для поля размером \(5\times 4\). Волна запущена из клетки (3, 3) и была остановлена после трех итераций. Белые клетки – клетки, не покрытые волной, серые и черные – клетки, покрытые волной. Клетки, покрытые волной на последней итерации, отмечены серым цветом.

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

В первой строке входного файла содержатся три целых числа через пробел \(N\), \(M\) и \(K\) (\(1 \leq N, M \leq 100\), \(1 \leq K \leq N + M\)). Следующие \(N\) строк содержат по \(M\) чисел, каждое из которых не превосходит \(10000\) по абсолютной величине.

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

Выведите четыре числа \(R\), \(C\), \(P\) и \(S\), где \(R\) – номер строки, \(C\) – номер столбца, из которых следует запустить волну, \(P\) – количество итераций распространения волны, \(S\) – максимальная сумма чисел, покрытых волной. Если существует несколько вариантов ответа, то вывести любой, в котором число \(P\) минимально. \(1 \leq P \leq K\).

Оценка

Решение, верно работающее при \(N, M \leq 15\) будет получать 50 баллов. Эти баллы выставляются при прохождении всех тестов группы. В оставшихся тестах \(N, M \leq 100\), эта группа оценивается при прохождении всех тестов группы.

Примеры
Входные данные
5   4   3
1   2   3   4
1   6   7   8
9  10  11  12 
0   0   0   0
2   0   0   1
Выходные данные
3  3  3  66
Страница: << 4 5 6 7 8 9 10 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест