Кошма вокруг юрты


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Внутреннюю стену юрты обивают войлоком. По кругу уже висят n кусков кошмы, кусок i весит a[i] килограммов; куски n и 1 тоже соседние. Мастер склеивает куски по два: берёт два соседних куска и склеивает их в один, на что уходит столько клея, сколько весят оба куска вместе. Склеенный кусок стоит на месте исходных, и его можно склеивать дальше.

Рисунок

Какое наименьшее количество клея нужно, чтобы склеить все куски в одну кошму?

Входные данные

В первой строке — число n (1 ≤ n ≤ 2000). Во второй строке — n чисел a[i] (1 ≤ a[i] ≤ 10⁹), по кругу.

Выходные данные

Выведите наименьшее количество клея.

Пример 1

Вход:

4
1 2 3 4

Выход:

19

Пояснение

Склеим куски 1 и 2 (клея 3), затем получившийся кусок с куском 3 (клея 6), затем с куском 4 (клея 10): всего 19.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n ≤ 40.

Подсказка

Оптимизация Кнута: если opt[i][j] — лучшая точка разреза отрезка [i, j], то opt[i][j − 1] ≤ opt[i][j] ≤ opt[i + 1][j].


Комментарии

Еще нет ни одного комментария.