#409

Максимальная сумма

Темы: [Динамическое программирование на таблицах]

Источники: [ Командные олимпиады, ВКОШП, 2006, Задача G ]

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

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

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

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

Напишите программу, которая по заданной таблице найдет искомый прямоугольник.

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

В первой строке вводятся два целых числа \(m\) и \(n\) (\(2 \le m, n \le 300\)). Далее следует описание таблицы – \(m\) строк, каждая из которых содержит по \(n\) целых чисел \(a_{i, j}\) (\(-10^4 \le a_{i,j} \le 10^4\)).

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

В первой строке выведите целое число \(s\) – максимальную сумму чисел на границе искомого прямоугольника. Во второй строке выведите четыре натуральных числа: \(x_1\), \(y_1\), \(x_2\), \(y_2\) – координаты левой верхней и правой нижней ячейки выбранного прямоугольника, соответственно (здесь \(x\) – номер строки, а \(y\) – номер столбца, строки нумеруются сверху вниз, начиная с единицы, столбцы нумеруются слева направо, начиная с единицы). Если оптимальных решений несколько, выведите любое.

Примеры

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

2 3
1 1 1
1 1 1

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

6
1 1 2 3

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

5 4
9 -2 -1 3
-10 -5 1 -4
1 -1 2 -2
3 0 0 -1
2 2 -1 2

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

8
3 1 5 3

#544

Космический мусорщик

Темы: [Динамическое программирование на таблицах]

Источники: [ Командные олимпиады, ВКОШП, 2002, Задача I ]

Вызов функции осуществляется с одним числовым параметром. Функция прибавляет один к счетчику и вызывает заданный набор функций с параметром, на 1 меньшим. При параметре 0 функция прекращает работу. Требуется вывести значение счетчика.

В околоземном космическом пространстве накопилось много мусора, поэтому ученые сконструировали специальный аппарат - ловушку для космического мусора. Для того, чтобы хорошо собирать мусор, этот аппарат должен двигаться по достаточно сложной траектории, сжигая собранный по пути мусор. Ловушка может передвигаться в пространстве по 6 направлениям: на север (\(N\)), на юг (\(S\)), на запад (\(W\)), на восток (\(E\)), вверх (\(U\)) и вниз (\(D\)). Движением ловушки управляет процессор. Программа движения задается шестью правилами движения, которые соответствуют каждому из указанных направлений. Каждое такое правило представляет собой строку символов из множества {\(N\), \(S\), \(W\), \(E\), \(U\), \(D\)}.

Команда ловушки есть пара из символа направления и параметра - целого положительного числа \(M\). При исполнении такой команды ловушка в соответствии со своей программой выполняет следующее. Если параметр больше 1, то она перемещается на один метр в направлении, которое указано в команде, а затем последовательно выполняет команды, заданные правилом для данного направления, с параметром меньше на 1. Если же параметр равен 1, то просто перемещается на один метр в указанном направлении.

Пусть, например, заданы следующие правила:

Тогда при выполнении команды \(S\)(3) мусорщик выполнит следующие действия:

1) переместится на 1 метр в направлении \(S\)
2) выполнит последовательно команды \(N\)(2), \(U\)(2), \(S\)(2), \(D\)(2), \(D\)(2), \(U\)(2), \(S\)(2), \(E\)(2).
Если далее проанализировать действия мусорщика при выполнении команд из пункта 2, получим, что в целом он совершит следующие перемещения:

SNNUUSNUSDDUSEDWEDDWEDUUSNUSDDUSEEПо заданной команде определите, какое общее количество перемещений на один метр совершит ловушка при выполнении заданной команды. В приведенном примере это количество равно 34.

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

Первые шесть строк входных данных задают правила для команд с направлением \(N\), \(S\), \(W\), \(E\), \(U\) и \(D\) соответственно. Каждая строка содержит не более 100 символов (и может быть пустой). Следующая строка содержит команду ловушки: сначала символ из множества {\(N\), \(S\), \(W\), \(E\), \(U\), \(D\)}, затем пробел и параметр команды - целое положительное число, не превышающее 100.

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

Выведите единственное число - количество перемещений, которое совершит ловушка. Гарантируется, что ответ не превышает \(10^9\).

Примеры

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

N
NUSDDUSE
UEWWD

U
WED
S 3

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

#572

Пузырьки 1D

Темы: [Динамическое программирование на таблицах]

Источники: [ Командные олимпиады, ВКОШП, 2007, Задача A ]

Задан одномерный массив "пузырьков", каждый из которых может быть одного из четырех цветов. Можно уничтожить группу подряд идущих пузырьков одинакового цвета и получить за это \(K^2\) очков (K - количество пузырьков). Требуется уничтожить все пузырьки и подсчитать максимальную сумму очков.

Сережа - большой любитель игр на сотовом телефоне. Недавно он скачал из интернета новую игру "Пузырьки 1D". Опишем правила игры.

Исходная позиция в игре представляет собой \(N\) пузырьков, расположенных вертикально в ряд. Каждый пузырек окрашен в один из четырех цветов - красный, зеленый, синий или желтый. Назовем группой несколько следующих подряд пузырьков одинакового цвета, непосредственно сверху и снизу от которых находятся либо пузырьки другого цвета, либо границы ряда пузырьков.

За один ход разрешается выбрать любую группу, состоящую хотя бы из двух пузырьков, и взорвать ее. За взрыв группы, содержащей K пузырьков, игрок получает K² очков. После взрыва группы пузырьки, которые находились сверху, опускаются вниз.

Например, ниже на рисунке показана позиция, содержащая 10 пузырьков. В ней четыре группы, содержащие 3, 2, 4 и 1 пузырек, соответственно. Если взорвать группу, содержащую четыре пузырька, то игрок получит 16 очков, и верхние 5 пузырьков опустятся вниз. В получившейся позиции 6 пузырьков, и две группы по 3 пузырька в каждой.

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

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

На вход программы поступает одна строка, состоящая из букв "R", "G", "B и "Y", описывающая начальную позицию. Буквы задают цвета пузырьков в порядке просмотра сверху вниз ("R" означает красный пузырек, "G" – зеленый, "B" – синий, а "Y" – желтый). В заданной позиции не менее двух и не более 100 пузырьков.

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

Выведите одно число – максимальное количество очков, которое сможет заработать Сережа. Если уничтожить все пузырьки невозможно, выведите 0.

Пояснения

В первом примере следует действовать следующим образом: сначала надо взорвать группу из четырех красных пузырьков, получив 16 очков. Затем надо взорвать в любом порядке получившиеся две группы по 3 пузырька, получив по 9 очков за каждую.

Примеры

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

RRRGGRRRRG

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

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

RB

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

#582

Движение по полосам

Темы: [Динамическое программирование на таблицах]

Источники: [ Командные олимпиады, ВКОШП, 2007, Задача K ]

K полос дороги расходятся по M направлениям. При этом в одном направлении может переходить несколько соседних полос (не менее одной). Требуется определить количество вариантов перехода полос в направления.

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

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

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

1. если с \(i\)-й полосы разрешено движение в \(a\)-м направлении, а с \(j\)-й полосы - в \(b\)-м направлении, причем \(i\) < \(j\), то \(a\) <= \(b\);
2. с каждой полосы разрешено движение хотя бы в одном направлении;
3. в каждом направлении разрешено движение хотя бы с одной полосы.

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

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

На вход программы поступают два целых числа: \(m\) и \(n\) (2 <= \(m\) <= 50, 1 <= \(n\) <= 15).

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

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

Пояснение к примеру

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

Примеры

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

4 2

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