ACMP 683

Ссылка на задачу

• ACMP #683 — Числа — 3

Комментарии

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

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

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

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