eolymp
bolt
Try our new interface for solving problems
Məsələlər

Оптимальное умножение матриц

Оптимальное умножение матриц

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Имея две матрицы A и B, мы можем вычислить C = AB используя стандартные правила умножения матриц:

prb1521

Число колонок в матрице A должно совпадать с числом строк матрицы B. Пусть матрица A имеет размер m × n, матрица B имеет размер n × p. Тогда матрица С будет иметь размер m × p, а для ее вычисления следует совершить m * n * p умножений.

prb1521_4.gif

Например, если A имеет размер 10 × 20, B имеет размер 20 × 15, то необходимо совершить 10 × 20 × 15 = 3000 умножений для вычисления матрицы C.

prb1521_3.gif

Перемножать несколько матриц можно несколькими способами. Например, если у нас имеются матрицы X, Y и Z, то вычислить XYZ можно либо как (XY)Z, либо как X(YZ). Пусть X имеет размер 5 × 10, Y имеет размер 10 × 20, Z имеет размер 20 × 35.

prb1521.gif

Подсчитаем количество умножений, необходимых для перемножения трех матриц в каждом из этих двух случаях:

(XY)Z

  • 5 × 20 × 10 = 1000 умножений для определения матрицы (XY), имеющей размер 5 × 20.

  • Потом 5 × 35 × 20 = 3500 умножений для нахождения конечного результата.

  • Общее количество умножений: 4500.

X(YZ)

  • 10 × 35 × 20 = 7000 умножений для определения матрицы (YZ), имеющей размер 10 × 35.

  • Потом 5 × 35 × 10 умножений для нахождения конечного результата.

  • Общее количество умножений: 8750.

Очевидно, что при вычислении (XY)Z требуется меньшее количество умножений.

prb1521_2.gif

По заданной последовательности перемножаемых матриц следует найти оптимальный порядок их умножения. Оптимальным называется такой порядок умножения матриц, при котором количество элементарных умножений минимально.

Giriş verilənləri

Первая строка содержит количество n (n10) перемножаемых матриц. Далее следуют n пар целых чисел, описывающих количество строк и столбцов в матрице, размеры матриц задаются в порядке их перемножения.

Çıxış verilənləri

Выведите минимальное количество умножений, достаточное для перемножения всех матриц.

Nümunə

Giriş verilənləri #1
3
5 10
10 20
20 35
Çıxış verilənləri #1
4500
Müəllif Михаил Медведев