TOJ2680: 最大矩阵连乘次数
最大 矩阵 次数
2023-09-14 09:11:41 时间
2680: 最大矩阵连乘次数 ![分享至QQ空间](http://210.33.181.162/acmhome/forum/images/ico_qzone.gif)
Time Limit(Common/Java):1000MS/10000MS Memory Limit:65536KByte
Total Submit: 144 Accepted:77
Total Submit: 144 Accepted:77
Description
给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最大。
Input
输入包含多组测试数据。第一行为一个整数C,表示有C组测试数据,接下来有2*C行数据,每组测试数据占2行,每组测试数据第一行是1个整数n(n≤10),表示有n个矩阵连乘,接下来一行有n+1个数,表示是n个矩阵的行及第n个矩阵的列,它们之间用空格隔开。
Output
你的输出应该有C行,即每组测试数据的输出占一行,它是计算出的矩阵最大连乘积次数。
Sample Input
1
3
10 100 5 50
Sample Output
75000
Source
矩阵乘法满足结合律
#include <stdio.h> int w,n,p[30],m[30][30],s[30][30]; int main() { scanf("%d",&w); while(w--) { scanf("%d",&n); for(int i=0; i<=n; i++) scanf("%d",&p[i]); for(int i=1; i<=n; i++) m[i][i]=0; for(int r=2; r<=n; r++) for(int i=1; i<=n-r+1; i++) { int j=r+i-1; m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; s[i][j]=i; for(int k=i+1; k<j; k++) { int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; if(t>m[i][j]) { m[i][j]=t; s[i][j]=k; } } } printf("%d\n",m[1][n]); } return 0; }
相关文章
- nyoj 最大和 104 (二维子矩阵 DP) 好题
- 蓝桥杯-算法训练2 最大最小公倍数
- Java实现第八届蓝桥杯最大公共子串
- Java实现二分图的最大权匹配
- Java 蓝桥杯 算法训练(VIP) 最大体积
- LeetCode: 221_Maximal Square | 二维0-1矩阵中计算包含1的最大正方形的面积 | Medium
- 矩阵的最大秩分解
- 812. 最大三角形面积
- 练习 3-4 在数的对二的补码表示中,我们编写的itoa函数不能处理最大的负数,即n等于-2字长-1的i情况。请解释其原因。修改该函数,使它在任何机器上运行时都能打印出正确的值。
- PHP上传文件超过了最大文件大小限制导致无法上传成功
- 第十三届蓝桥杯JavaB组省赛F题——最大子矩阵 (AC)