L. Триангуляция многоугольника

В вершинах выпуклого многоугольника написаны числа. Многоугольник разрезают диагоналями на треугольники; стоимость треугольника - произведение чисел в его вершинах. Найдите наименьшую суммарную стоимость.

Состояние - отрезок вершин по контуру. $dp[i][j]$ - наименьшая стоимость триангуляции многоугольника на вершинах $i, i+1, \ldots, j$.

Ребро $(i, j)$ входит ровно в один треугольник; переберём его третью вершину $k$:

База: $dp[i][i+1] = 0$, вырожденный «многоугольник» из двух вершин ничего не стоит.

Обратите внимание, насколько это похоже на умножение матриц - и всё же не то же самое: там разрез шёл по промежуткам между матрицами, здесь по вершинам, и потому $dp[k][j]$, а не $dp[k+1][j]$. Такие сдвиги на единицу - главный источник ошибок во всей теме; выписывайте, что именно обозначает индекс.

При $n \le 300$ и числах до 100 ответ доходит до $3 \cdot 10^8$ - помещается в 32 бита, но привычка считать в 64 дешевле.

В первой строке - число $n$ ($3 \le n \le 300$) - количество вершин.

Во второй строке - $n$ чисел $a_i$ ($1 \le a_i \le 100$) в порядке обхода.

Одно число - наименьшая стоимость триангуляции.