ZOJ 1094 Matrix Chain Multiplication

ZOJ 1094 Matrix Chain Multiplication

矩阵链乘的时候,不同的结合方式所需要的运算次数不同,肯定存在一个乘法次数最少的结合方式(可以用dp求出),此题以此为背景,给出结合方式,求出所需要的乘法次数.算是经典的栈的应用,维护两个栈,KUO是括号的栈,M表示矩阵栈,从每一个表达式的开始,遇到左括号和矩阵就压入相应的栈,遇到右括号就进行栈顶两个元素的运算,直到最后。如果某两个元素不能相乘,输出error

(更多…)

继续阅读 →