本文出自 http://blog.csdn.net/shuangde800
题目大意
给出一系列的矩阵,给他们取名A ,B…… 并且给出了它们的行数和列数。给完后,给出一系列的表达式,然后要求求出按这些表达式进行计算,会有多少次乘法步骤。
思路
这题去年的暑假是有做过的,在《入门经典》的数据结构专题 ...打开
现在在看一年前的代码,无论是方法还是代码都觉得不是一般地搓 - -||
在过几个月后看今天写的代码还是会觉得搓吧。
不过这次既然归到了dp专题,那么就用dp的方法来做吧。
(以上是题外话)
很明显看出可以递归求解,而且可转为递推区间dp求解
f(i, j) 表示在(i,j)区间中一共有几次相乘
row(i, j)表示这个区间相乘后的矩形行尺寸
col(i, j) 表示这个区间相乘后的矩形列尺寸
递归时维护这三个数组即可
那么如果str[i]='('且str[j]=')', 就递推求解子问题f(i+1, j-1)
如果只有一边是括号,那么递推求解f(i+1, j) 和 f(i, j-1)
接着枚举终点k, 当这个划分合法时:
f(i, j) = f(i,k) + f(i,k+1) + row(i,k)*row(k+1,j)*col(k+1,j)
代码
<script src="https://code.csdn.net/snippets/568.js" type="text/javascript"></script>
分享到:
相关推荐
在三值光学计算机上进行的矢量乘矩阵运算,金翊,王先超,本文报道一种进行矢量乘矩阵运算的光学方法。这个方法在一种新颖的光学计算结构--三值光学计算机(ternary optical computer,TOC)上,使�
lvds-source-synch-serdes-clock-multiplication.pdf
Source Code for 2009 Supercomputing Paper Implementing Sparse Matrix-Vector Multiplication on Throughput-Oriented Processors
matrix multiplication (see laochanlam/matrix-multiplication in github)
...The number of questions is increasing recently. Here is the classification of all `468` questions. ...I'll keep updating for full summary and better solutions....|-----|---------------- | --------------- |...
| |-- matrix.py | |-- magnitude.py | |-- dot_product.py | |-- column.py | |-- additions.py | |-- scalar.py | |-- multiplication.py | |-- determinant.py | |-- cofactors.py | |-- minors.py | |...
矩阵链乘法 该程序找到了最有效的乘法矩阵的方法。 该程序实现的复杂度为O(n ^ 3),并用O(n)括住最终输出 输入规范:第一行包含n,下一行包含a0,...,an,以空格分隔。 假定所有数字都是正数且适合int且n最多为...
Matrix Chain Multiplication is perhaps the quintessential example of dynamic programming. The problem can be stated as follows: given a chain <A1, A2,..., An> of n matrices, where for i = 1, 2,....
Efficient matrix multiplication
MaskNet:Introducing+Feature-Wise+Multiplication+to+CTR+Ranking+Models+by+Instance-Guided+Mask
Synchronous-100x100-Matrix-Multiplication-using-Multiple-Threads:开发了一个程序,用于通过使用多个线程将两个大型矩阵相乘。 之后,通过在有效时间内将整个任务划分为不同数量的线程来同步计算结果矩阵
the new algorithm is also faster than the best known matrix multiplication algorithm for dense matrices which uses O(n2:38) algebraic operations. The new algorithm is obtained using a surprisingly ...
用法 $ npm install$ NODE_PATH=node_modules node index.js [DONE] RESET DATABASE[ '[DONE] generate test data: leftMatrix: ', [ { row: 0, column: 0, value: 0, _id: 54a0219b5c38d4e4722b9c8f }, { row: 0, ...
题目描述: 输入n个矩阵的维度和一些矩阵链乘表达式,输出乘法的次数。如果乘法无法进行,输出error。假定A是m*n矩阵,B是n*p矩阵,那么AB是m*p矩阵,乘法次数为m*n*p。如果A的列数和B的行数不同,则乘法无法进行。...
struct Matrix { int a, b; Matrix(int a = 0,int b=0):a(a),b(b){} }m[26]; stack s; int main() { int n; cin >> n; for (int i = 0; i > name; int k = name[0] - 'A'; cin >> m[k].a >> m[k].b; } ...
see jaeho3690/Matrix_multiplication_python in github
矩阵向量乘法 该算法的描述可以参考 。
稀疏矩阵乘法 稀疏矩阵乘法
矩阵乘法集群 该项目暗示了分布式计算体系结构可以执行矩阵乘法。 该项目的主要依存关系是ZeroMQ。 该程序在IPC机制上运行。 运行程序 请按照以下步骤运行代码 启动服务器: 服务器负责接收来自客户端的请求;...