Войти Регистрация
Алгоритмы

85. Склейка соседних партий на сортировке

Сложная

На ленте сортировочного центра Ozon стоят n партий подряд, weights[i] — число посылок в i-й. За один шаг две соседние партии объединяют в одну, это стоит столько, сколько посылок в обеих.

Через n - 1 шагов остаётся одна партия. Верните минимальную суммарную стоимость. Для одной партии ответ 0.

В работе: Порядок слияния соседних сегментов индекса или партий на складе, когда переставлять их нельзя.

Пример 1

Ввод
weights = [4, 1, 3]
Вывод
12

Сначала 1+3=4, потом 4+4=8: итого 12. Если начать с 4+1, выйдет 5+8=13.

Пример 2

Ввод
weights = [7]
Вывод
0

Склеивать нечего.

Ограничения

  • 1 ≤ длина weights ≤ 2000
  • 1 ≤ weights[i] ≤ 1000
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def merge_batches(weights):
ДП на отрезкахОптимизация КнутаПрефиксные суммыцельn2

Источник: наша задача на данных Ozon. Условие пересказано своими словами.