Просмотр кода страницы ACMP 683

== Ссылка на задачу ==
* [http://acmp.ru/?main=task&id_task=683 ACMP #683 &mdash; Числа &mdash; 3]

== Комментарии ==

Вид подзадачи: d[l][r] &mdash; минимальный штраф за удаление отрезка a[l]..a[r]. 

Рекуррентная формула: d[l][r] = min(d[l][i] + a[i] &times; (a[l] + a[r]) + d[i][r]), где i &isin; (l + 1)..(r - 1).

База рекурсии: Если l + 1 >= r, то d[l][r] = 0.

Вид ответа: d[0][n - 1]. Сложность O(N<sup>2</sup>).

[[Category: Сборник задач: ACMP]]
[[Category: Задачи: Динамическое программирование &mdash; подотрезок]]