Задача 102787
|
Название задачи: Жадный калькулятор . |
 |
Условие
Задано алгебраическое выражение, составленное из неотрицательных вещественных чисел и знаков операций +, - и ?. Требуется так расставить в этом выражении скобки, чтобы его значение стало максимально возможным.Входные данные
Исходное выражение длиной не более 250 символов записано в первой строке входного файла. Выражение содержит не более 50 чисел, каждое из которых лежит в диапазоне от 0 до 106 . Пробелы внутри чисел не допускаются.
Выходные данные
Выведите в первую строку выходного файла максимально возможное после расстановки скобок значение выражения, а во вторую строку – само это выражение (если вариантов несколько, нужно выдать любой из них).
Пример входного файла
1+2 - 3.0*4
Пример выходного файла
0
((1+2)-3)*4
Решение
Скачать архив тестов и решенийПусть задано некоторое алгебраическое выражение, содержащее N чисел. Рассмотрим кусок этого выражения, расположенный между i-м и j-м его числами включительно (1 ≤ i ≤ j ≤ N). Пусть Max(i, j) обозначает максимально возможное после расстановки скобок значение этого куска, а Min(i, j) – минимально возможное. Эти числа следует вычислять парами в порядке увеличения длин кусков j-i+1. Ясно, что для всех i от 1 до N значения Max(i, i) и Min(i, i) совпадают и равны i-му числу выражения. При i < j число Max(i, j) вычисляем следующим образом. Перебираем все значения k, такие что i ≤ k < j, и каждый раз предполагаем, что при вычислении значения рассматриваемого куска самой последней выполняется операция, записанная между числами с номерами k и k+1. Если это, к примеру, операция вычитания, то чтобы максимизировать значение части выражения от i-го числа до j-го, мы должны взять максимальное значение куска от i-го числа до k-го (которое уже вычислено) и вычесть из него минимальное значение куска от (k+1)-го числа до j-го (которое также уже вычислено). Из значений, полученных при анализе различных k, выбираем максимальное. Операции + и * и вычисление Min(i, j) рассматриваются аналогично.
