Задача
Имея два двумерных массива $A$ и $B$, мы можем вычислить $C = AB$ используя стандартные правила умножения матриц:
$$C_{ij} = \sum_{k}A_{ik}{Bkj}$$
Число колонок в массиве $A$ должно совпадать с числом строк массива $B$. Обозначим через $rows(A)$ и $columns(A)$ соответственно количество строк и колонок в массиве $A.$ Количество умножений, необходимых для вычисления матрицы $C$ (ее количество строк совпадает с $A$, а количество столбцов с $B$) равно $rows(A)$ $columns(B)$ $columns(A).$ Например, если A имеет размер 10 × 20, B имеет размер 20 × 15, то для их умножения необходимо совершить 10 × 15 × 20, или 3000 умножений для вычисления матрицы $C.$
Перемножать несколько матриц можно несколькими способами. Например, если у нас имеются матрицы $X$, $Y$ и $Z$, то вычислить $XYZ$ можно либо как $(XY)Z$, либо как $X(YZ)$. Пусть $X$ имеет размер 5 × 10, $Y$ имеет размер 10 × 20, $Z$ имеет размер 20 × 35. Подсчитаем количество умножений, необходимых для перемножения трех матриц в каждом из этих двух случаях:
$(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$ требуется меньшее количество умножений.
По заданной последовательности перемножаемых матриц следует найти оптимальный порядок их умножения. Оптимальным называется такой порядок умножения матриц, при котором количество элементарных умножений минимально.
Входные данные
Для каждой последовательности перемножаемых матриц Вам будут даны лишь размеры матриц. Каждый тест состоит из количества $n (n \leq 10)$ перемножаемых матриц, за которым следуют $n$ пар целых чисел, описывающих размеры матриц (количество строк и столбцов); размеры матриц задаются в порядке их перемножения. Последний тест содержит $n = 0$ и не обрабатывается.
Выходные данные
Пусть матрицы пронумерованы $A1, A2,\ldots, An.$ Для каждого теста в отдельной строке следует вывести его номер и скобочное выражение, содержащее оптимальный порядок умножения матриц. Тесты нумеруются начиная с 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))
|
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))
|
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)
|
Код программы
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
import java.util.Scanner; public class Main { private static class Matrix { private int width; private int height; public Matrix(int width, int height) { this.width = width; this.height = height; } } private static long multiple(long[][] dp, Matrix[] sizes, int[][] bestCut, int l, int r ) { if (dp[l][r] == Long.MAX_VALUE) { for (int i = l; i < r; i++) { long cur = multiple(dp, sizes, bestCut, l, i) + multiple(dp, sizes, bestCut, i + 1, r) + sizes[l].width * sizes[i].height * sizes[r].height; if (cur < dp[l][r]) { dp[l][r] = cur; bestCut[l][r] = i; } } } return dp[l][r]; } private static void print(int l, int r, int[][] bestCut) { if (l == r) { System.out.print("A" + (l + 1)); } else { System.out.print("("); print(l, bestCut[l][r], bestCut); System.out.print(" x "); print(bestCut[l][r] + 1, r, bestCut); System.out.print(")"); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); for (int c = 1, n = sc.nextInt(); n != 0; n = sc.nextInt(), c++) { long[][] dp = new long[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dp[i][j] = Long.MAX_VALUE; } } Matrix[] sizes = new Matrix[n]; int[][] bestCut = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { bestCut[i][j] = Integer.MAX_VALUE; } } for (int i = 0; i < n; i++) { int width = sc.nextInt(); int height = sc.nextInt(); sizes[i] = new Matrix(width, height); } for (int i = 0; i < n; i++) { dp[i][i] = 0; } multiple(dp, sizes, bestCut, 0, n-1); System.out.print("Case " + c + ": "); print(0, n - 1, bestCut); System.out.println(); } } } |
Решение задачи
Обозначим результат перемножения матриц ${\displaystyle A_{i}A_{(i+1)}…A_{j}}$ ${\displaystyle A_{i}A_{(i+1)}…A_{j}}$ через ${\displaystyle A_{i..j}}$ ${\displaystyle A_{i..j}}$, где i\leq j. Если i<j, то существует такое k, которое разбивает ${\displaystyle A_{i..j}}$ ${\displaystyle A_{i..j}}$ между матрицами ${\displaystyle A_{k}}$ A_k и ${\displaystyle A_{k+1}}$ A_${{k+1}}$, i\leq k<j. То есть для вычисления ${\displaystyle A_{i..j}}$ ${\displaystyle A_{i..j}}$ надо сначала вычислить ${\displaystyle A_{i..k}}$ ${\displaystyle A_{i..k}}$, потом ${\displaystyle A_{k+1..j}}$ ${\displaystyle A_{k+1..j}}$ и затем их перемножить. Выбор $k$ является аналогом расстановки скобок между матрицами. Выбрав некоторое $k$ мы свели задачу к двум аналогичным подзадачам для матриц ${\displaystyle A_{i..k}}$ ${\displaystyle A_{i..k}}$ и ${\displaystyle A_{k+1..j}}$ ${\displaystyle A_{k+1..j}}.$ Объясняется оно просто: для того, чтобы найти произведение матриц ${\displaystyle A_{i..j}}$ ${\displaystyle A_{i..j}}$ при i=j не нужно ничего делать — это и есть сама матрица ${\displaystyle A_{i}}$ A_${i}.$ При нетривиальном случае мы перебираем все точки разбиения матрицы ${\displaystyle A_{i..j}}$ ${\displaystyle A_{i..j}}$ на матрицы ${\displaystyle A_{i..k}}$ ${\displaystyle A_{i..k}}$ и ${\displaystyle A_{k+1..j}}$ ${\displaystyle A_{k+1..j}}$, ищем кол-во операций, необходимое чтобы их получить и затем перемножаем для получения матрицы ${\displaystyle A_{i..j}}$ ${\displaystyle A_{i..j}}.$ (Оно будет равно кол-ву операций, потраченное на решение подзадач + стоимость умножения матриц ${\displaystyle A_{i..k}A_{k+1..j}}$ ${\displaystyle A_{i..k}A_{k+1..j}}$). Считаем, что размеры матриц заданы в массиве ${\displaystyle p}$ p и размер матрицы ${\displaystyle A_{i}}$ A_${i}$ равен ${\displaystyle p_{i-1}\times p_{i}}$ ${\displaystyle p_{i-1}\times p_{i}}.$ Будем запоминать в двумерном массиве m результаты вычислений для подзадач, чтобы избежать пересчета для уже вычислявшихся подзадач.
Ссылки
Описание алгоритма решения
Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone
Например, замостить прямоугольник $2 × 3$ можно только тремя различными способами. Поскольку ответ может быть достаточно большим, искомое количество способов следует вычислять по модулю $10^6$.
