蓝桥矩阵乘法（区间dp）

秒速五厘米 2022-05-28 07:39 128阅读 0赞

算法提高 矩阵乘法

时间限制：3.0s   内存限制：256.0MB

问题描述

有n个矩阵，大小分别为a0\*a1, a1\*a2, a2\*a3, ..., a\[n-1\]\*a\[n\]，现要将它们依次相乘，只能使用结合率，求最少需要多少次运算。  
　　两个大小分别为p\*q和q\*r的矩阵相乘时的运算次数计为p\*q\*r。

输入格式

输入的第一行包含一个整数n，表示矩阵的个数。  
　　第二行包含n+1个数，表示给定的矩阵。

输出格式

输出一个整数，表示最少的运算次数。

样例输入

3  
1 10 5 20

样例输出

150

数据规模和约定

1<=n<=1000, 1<=ai<=10000。

#include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn=1e3+10;
    typedef long long ll;
    const ll INF=9999999999999;
    ll dp[maxn][maxn];
    ll num[maxn];
    int n;
    
    void init(){
    	for(int i=1; i<=n; i++)
    	{
    		for(int j=1; j<=n; j++)
    		{
    			dp[i][j]= i==j? 0 : INF;
    		}
    	}
    	
    }
    
    int main(){
    	scanf("%d", &n);
    	
    	for(int i=0; i<=n; i++)
    		scanf("%d", &num[i]);
    	
    	init();
    	
    	for(int k=1; k<n; k++)
    	{
    		for(int i=1; i+k<=n; i++)
    		{
    			int j=i+k;  
    			for(int t=i; t<j; t++)
    				dp[i][j]= min(dp[i][j], dp[i][t]+dp[t+1][j]+num[i-1]*num[t]*num[j]);
    		}
    	}
    	
    	printf("%lld\n", dp[1][n]);
    	
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，128人围观）

还没有评论，来说两句吧...

相关阅读

相关蓝桥杯算法训练 ALGO-60 矩阵乘法

算法训练矩阵乘方时间限制：1.0s 内存限制：512.0MB 问题描述　　给定一个矩阵A,一个非负整数b和一个正整数m，求A的b次方除m的余数。　　其中一个n

迷南。/ 2023年10月06日 09:42/ 0 赞/ 76 阅读

相关【蓝桥杯】ALGO-86 矩阵乘法

资源限制时间限制：1.0s 内存限制：512.0MB 问题描述　　输入两个矩阵，分别是ms，sn大小。输出两个矩阵相乘的结果。输入格式　　第一行，空

谁践踏了优雅/ 2022年12月04日 07:42/ 0 赞/ 126 阅读

相关算法提高矩阵乘法（区间dp）

问题描述　　有n个矩阵，大小分别为a0\a1, a1\a2, a2\a3, ..., a\[n-1\]\a\[n\]，现要将它们依次相乘，只能使用结合率，求最少需要多少次运

清疚/ 2022年09月28日 05:52/ 0 赞/ 130 阅读

相关 dp 最优矩阵乘法

该题题意如下描述有若干个矩阵\{Ai\}，元素都为整数且已知矩阵大小。如果要计算所有矩阵的乘积A1 \ A2 \ A3 .. Am，最少要多少次整数乘法？

小咪咪/ 2022年06月13日 08:42/ 0 赞/ 145 阅读

相关蓝桥杯算法训练矩阵乘法

![这里写图片描述][SouthEast] import java.util.Scanner; public class Main {

ゝ一纸荒年。/ 2022年06月01日 01:20/ 0 赞/ 178 阅读

相关蓝桥垒骰子（dp+矩阵快速幂）

垒骰子赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。经过长期观察，atm 发现了稳定骰子的奥秘：有

偏执的太偏执、/ 2022年05月29日 12:46/ 0 赞/ 152 阅读

相关蓝桥石子合并（区间DP四边形不等式）

算法提高合并石子时间限制：2.0s 内存限制：256.0MB 问题描述　　在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子

古城微笑少年丶/ 2022年05月29日 07:53/ 0 赞/ 186 阅读

相关蓝桥矩阵乘法（区间dp）

算法提高矩阵乘法时间限制：3.0s 内存限制：256.0MB 问题描述　　有n个矩阵，大小分别为a0\a1, a1\a2, a2\a3,

秒速五厘米/ 2022年05月28日 07:39/ 0 赞/ 129 阅读

相关矩阵乘法基础训练-蓝桥杯

> 注意，当m==0时，输出单位矩阵。题目描述给定一个N阶矩阵A，输出A的M次幂（M是非负整数）例如： A = 1 2 3 4 A

Bertha 。/ 2022年03月24日 15:40/ 0 赞/ 284 阅读

相关蓝桥杯基础练习矩阵乘法

问题描述　　给定一个N阶矩阵A，输出A的M次幂（M是非负整数）　　例如：　　A = 　　1 2 　　3 4 　　A

比眉伴天荒/ 2022年03月22日 16:52/ 0 赞/ 204 阅读