首页 > 代码库 > 算法提高 矩阵乘法 区间dp
算法提高 矩阵乘法 区间dp
问题描述
有n个矩阵，大小分别为a0*a1, a1*a2, a2*a3, ..., a[n-1]*a[n]，现要将它们依次相乘，只能使用结合率，求最少需要多少次运算。
两个大小分别为p*q和q*r的矩阵相乘时的运算次数计为p*q*r。
两个大小分别为p*q和q*r的矩阵相乘时的运算次数计为p*q*r。
输入格式
输入的第一行包含一个整数n，表示矩阵的个数。
第二行包含n+1个数，表示给定的矩阵。
第二行包含n+1个数，表示给定的矩阵。
输出格式
输出一个整数，表示最少的运算次数。
样例输入
3
1 10 5 20
1 10 5 20
样例输出
150
数据规模和约定
1<=n<=1000, 1<=ai<=10000。
1 #include<bits/stdc++.h> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #include<algorithm> 6 #include<vector> 7 #define ll __int64 8 #define PI acos(-1.0) 9 using namespace std;10 int n;11 ll a[1005];12 ll score[1005][1005];13 int main()14 {15 scanf("%d",&n);16 for(int i=1; i<=n+1; i++)17 scanf("%I64d",&a[i]);18 memset(score,0,sizeof(score));19 for(int i=1; i<=n+1; i++)20 for(int j=1; j<=n+1; j++)21 score[i][j]=1000000000000000;22 for(int i=1; i<=n; i++)23 score[i][i+1]=0ll;24 for(int i=n+1; i>=1; i--)25 {26 for(int j=i+1; j<=n+1; j++)27 {28 for(int k=i+1; k<j; k++)29 score[i][j]=min(score[i][j],score[i][k]+score[k][j]+a[k]*a[i]*a[j]);30 }31 }32 printf("%I64d\n",score[1][n+1]);33 return 0;34 }
算法提高 矩阵乘法 区间dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。