UVA442 矩阵链乘 Matrix Chain Multiplication

    • 143通过
    • 249提交
  • 题目来源 UVA 442
  • 评测方式 RemoteJudge
  • 标签 字符串 构造
  • 难度 普及/提高-
  • 时空限制 3000ms / 0MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    矩阵链乘

    题目描述

    ​ 假设你必须评估一种表达形如 ABCDE,其中 A,B,C,D,E是矩阵。既然矩阵乘法是关联的,那么乘法的顺序是任意的。然而,链乘的元素数量必须由你选择的赋值顺序决定。

    ​ 例如,A,B,C分别是 50 10 ,10 20 和 20 5 的矩阵。现在有两种方案计算 A B C ,即(A B) C 和 A(B * C)。
    第一个要进行15000次基本乘法,而第二个只进行3500次。

    ​ 你的任务就是写出一个程序判定以给定的方式相乘需要多少次基本乘法计算。

    输入格式

    ​ 输入包含两个部分:矩阵和表达式。 输入文件的第一行包含了一个整数 n(1 $\leq$ n $\leq$ 26), 代表矩阵的个数。接下来的n行每一行都包含了一个大写字母,说明矩阵的名称,以及两个整数,说明行与列的个数。
    第二个部分严格遵守以下的语法:

    SecondPart = Line { Line } <EOF> Line = Expression <CR> Expression = Matrix | "(" Expression Expression ")" Matrix = "A" | "B" | "C" | ... | "X" | "Y" | "Z"

    输出格式

    ​ 对于每一个表达式,如果乘法无法进行就输出 " error "。否则就输出一行包含计算所需的乘法次数。

    感谢@onceagain 提供翻译

    题目描述

    PDF

    输入输出格式

    输入格式:

    输出格式:

    输入输出样例

    输入样例#1: 复制
    9
    A 50 10
    B 10 20
    C 20 5
    D 30 35
    E 35 15
    F 15 5
    G 5 10
    H 10 20
    I 20 25
    A
    B
    C
    (AA)
    (AB)
    (AC)
    (A(BC))
    ((AB)C)
    (((((DE)F)G)H)I)
    (D(E(F(G(HI)))))
    ((D(EF))((GH)I))
    输出样例#1: 复制
    0
    0
    0
    error
    10000
    error
    3500
    15000
    40500
    47500
    15125
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。