Цепочка матриц
Отправить решение
Решать в редакторе
Сложность:
40%
Очки:
100 (частичный балл)
Ограничение по времени:
1.0s
Ограничение по памяти:
256M
Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch
Цепочка матриц
Нужно перемножить n матриц подряд. Матрица i имеет размер d_{i−1} × d_i. Умножение матриц размеров a×b и b×c стоит a·b·c операций. Расставив скобки наилучшим образом, найдите наименьшее число операций для вычисления всего произведения.
Ввод. В первой строке n (1 ≤ n ≤ 150), во второй n+1 чисел d_0…d_n (1 ≤ d_i ≤ 100).
Вывод. Наименьшее число операций.
Пример
Ввод:
3
10 30 5 60
Вывод:
4500
Комментарии