{"trustable":false,"sections":[{"title":"题目描述","value":{"format":"MD","content":"给出 $n$ 个矩阵 $A_1,A_2,\\cdots,A_n$ 的大小 $r_i\\times c_i$,现在要将求 $A_1A_2\\cdots A_n$,已知 $c_i\u003dr_{i+1}$,并且每次乘法次数是 $r_ic_{i+1}r_{i+1}$,求怎样乘法可以使得乘法次数最小。"}},{"title":"输入格式","value":{"format":"MD","content":"多组数据。第一个整数 $n$ 代表矩阵个数, $n\u003d0$ 代表数据结束;随后 $n$ 行每行两个整数代表矩阵大小 $r_i\\times c_i$。"}},{"title":"输出格式","value":{"format":"MD","content":"输出各个矩阵的乘法顺序。乘法必须加括号,因此可能的输出可以是 $(A_1\\times(A_2\\times A_3))$,并在乘法 `x` 左右加空格。在乘法的前面输出样例组数,即 `Case xx: `。"}},{"title":"样例输入","value":{"format":"MD","content":"```plaintext\n3\n1 5\n5 20\n20 1\n3\n5 10\n10 20\n20 35\n6\n30 35\n35 15\n15 5\n5 10\n10 20\n20 25\n0\n```"}},{"title":"样例输出","value":{"format":"MD","content":"```plaintext\nCase 1: (A1 x (A2 x A3))\nCase 2: ((A1 x A2) x A3)\nCase 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))\n```"}}]}