e-olymp 1521. Оптимальное умножение матриц

Задача

Имея два двумерных массива [latex]A[/latex] и [latex]B[/latex], мы можем вычислить [latex]C = AB[/latex] используя стандартные правила умножения матриц. Число колонок в массиве [latex]A[/latex] должно совпадать с числом строк массива [latex]B[/latex]. Обозначим через [latex]rows(A)[/latex] и [latex]columns(A)[/latex] соответственно количество строк и колонок в массиве [latex]A[/latex]. Количество умножений, необходимых для вычисления матрицы [latex]C[/latex] (ее количество строк совпадает с [latex]A[/latex], а количество столбцов с [latex]B[/latex]) равно [latex]rows(A) columns(B) columns(A)[/latex]. По заданной последовательности перемножаемых матриц следует найти оптимальный порядок их умножения. Оптимальным называется такой порядок умножения матриц, при котором количество элементарных умножений минимально.

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

Каждый тест состоит из количества [latex]n (n ≤ 10)[/latex] перемножаемых матриц, за которым следуют [latex]n[/latex] пар целых чисел, описывающих размеры матриц (количество строк и столбцов). Размеры матриц задаются в порядке их перемножения. Последний тест содержит [latex]n = 0[/latex] и не обрабатывается.

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

Пусть матрицы пронумерованы [latex]A_{1}[/latex], [latex]A_{2}[/latex],…, [latex]A_{n}[/latex]. Для каждого теста в отдельной строке следует вывести его номер и скобочное выражение, содержащее оптимальный порядок умножения матриц. Тесты нумеруются начиная с [latex]1[/latex]. Вывод должен строго соответствовать формату, приведенному в примере. Если существует несколько оптимальных порядков перемножения матриц, выведите любой из них.

Тесты

 №  Входные данные  Выходные данные
 1 3
1 5
5 20
20 1
3
5 10
10 20
20 35
6
30 35
35 15
15 5
5 10
10 20
20 25
0
Case 1: (A1 x (A2 x A3))
Case 2: ((A1 x A2) x A3)
Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))
 2  10
653 273
273 692
692 851
851 691
691 532
532 770
770 690
690 582
582 519
519 633
0
Case 1: (A1 x ((((((((A2 x A3) x A4) x A5) x A6) x A7) x A8) x A9) x A10))
 3  2
11 12
12 33
7
1 5
5 28
28 19
19 2
2 10
10 1
1 12
4
10 29
29 133
133 8
8 15
0
Case 1: (A1 x A2)
Case 2: (((((A1 x A2) x A3) x A4) x (A5 x A6)) x A7)
Case 3: ((A1 x (A2 x A3)) x A4)

Код программы

Засчитанное решение на e-olymp.com

Решение

Пусть [latex]A[/latex]- любая не последняя матрица заданной последовательности, [latex]B[/latex] — матрица, что следует за [latex]A[/latex] в данной последовательности перемножаемых матриц. Заведём двумерный массив [latex]dp[/latex] размером [latex] {(n+1)}\times {(n+1)}[/latex]. По главной диагонали массива запишем размеры матриц, причём [latex]rows(B)[/latex] не будем записывать, так как [latex]rows(B)=columns(A)[/latex]. В dp[k][j] [latex]\left( j<k \right) [/latex] будем хранить минимальное количество операций необходимое для получения матрицы [latex]C_{kj}[/latex] такой, что [latex]columns(C_{kj})[/latex] равно элементу dp[k][k], а [latex]rows(C_{kj})[/latex] соответственно dp[j][j]. Для получения матрицы [latex]C_{kj}[/latex] нужно умножить матрицу [latex]C_{k(j+t)}[/latex] на [latex]C_{(j+t)j}[/latex] [latex](\left( k-j \right) >t>0)[/latex], для этого нам понадобиться [latex]rows(C_{k(j+t)}) columns(C_{(j+t)j}) columns(C_{k(j+t)}) [/latex], что равно dp[k][k]*dp[j][j]*dp[j+t][j+t], операций непосредственно на перемножение этих матриц, а также dp[k][j+t] и dp[j+t][j] операций для получения матриц [latex]C_{k(j+t)}[/latex] и [latex]C_{(j+t)j}[/latex] соответственно.
Тогда dp[k][j]=dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t]. При помощи цикла подберём [latex] t [/latex], при котором значение dp[k][j] выходит минимальным. Для получения матриц, которые даны изначально, не требуется ни одной операции, поэтому диагональ массива прилегающую к главной диагонали оставим заполненной нулями. Далее, при помощи вложенных циклов на каждом шаге внешнего цикла будем заполнять диагональ массива, что расположена ниже предыдущей. Параллельно будем запоминать номер последнего умножения, который будет равен [latex]j+t[/latex], в элемент массива, который расположен симметрично  dp[k][j] относительно главной диагонали (то есть в dp[j][k]). Таким образом от умножения двух исходных матриц поэтапно перейдём к оптимальному произведению [latex]n[/latex] матриц. Затем, рекурсивно восстановим оптимальный порядок умножения матриц. Для вывода ответа в соответствующем формате также воспользуемся рекурсией.

Ссылки

Добавить комментарий