14
правок
Изменения
Нет описания правки
'''for''' j = i + 1 '''to''' n:
'''for''' k = i '''to''' j - 1:
d[i][j] = max(d[i][j], max(d[i][k] + d[k+1][j], d[i][k] * d[k + 1][j]));
'''print'''(d[1][n]); <font color="green">// вывод ответа</font>
| <tex>2</tex>
|}
== Восстановление ответа ==
С помощью описанного выше алгоритма можно восстановить оптимальное арифметическое выражение. Для этого нужно в таблице <tex>d</tex> хранить каким способом был получен оптимальный ответ. То есть будем хранить <tex>index</tex> {{---}} границу раздела на 2 подотрезка и <tex>operation</tex> {{---}} операцию совершенную над двумя отрезками (<tex>+, \times</tex>). В итоге для каждого отрезка мы будем знать какой знак и куда поставить. Для простоты будем заключать каждый полученный подотрезок в скобки. Таким образом мы получим выражение, в котором полностью расставлены скобки.
Для вышеприведенного примера ответ будет выглядеть так <tex> (2+1)\times(1+2)</tex>
== Решение задачи без возможности использования скобок ==
При условии задачи, в котором запрещено использовать скобки, вышеописанный алгоритм будет работать некорректно. Дело в том, что если на отрезке <tex>k\dots j</tex> была использована операция сложения, то мы не можем перемножить результаты на отрезке <tex>i\dots k - 1</tex> и отрезке <tex>k\dots j</tex>. Для решения этой проблемы будем использовать две матрицы <tex>d</tex> {{---}} такую же как и раньше, а также <tex>p</tex> <tex>(p[i][j]</tex> {{---}} произведение чисел <tex dpi = "130">a_i, a_{i+1}, \dots, a_j)</tex>. Тогда получим новую формулу пересчета динамики:
<br />
* <tex>d[i][j] = \max\limits_{\mathop{k = i..j-1}}[\max(d[i][k] + d[k + 1][j], p[i][k] \times p[k + 1][j])] \ (i < j)</tex> <br />
== Источники ==
